编写trie解析递归函数，节点跨越

Question

目的：此函数解析与输入的字符串匹配的路径之后的字符串trie。当字符串中的所有字符都被解析后，返回true。如果仍然存在有效的路径，我想跨越一个char并返回。

应用程序：字符串是公路项目的位置层次结构。因此，项目5具有对齐C，其具有N和工作区3的偏移; 5CN3。但是，有时我想为包含所有位置的项目任务的所有子位置定义一个字符串。所以，'0'是所有地点;对于半年的操作，如等级污垢没有工作区 - 所有代表此任务的都是北向对齐C中的所有工作区; 5CN0。如果一个操作覆盖整个项目，这也是一样的; 5000.

方法：我可以使用通配符'？'功能，但我想保留这个特定的步骤来抽象地点的目的。也许 '？'是正确的做法，但似乎放松了一些控制。此外，这可以写入没有for循环，并使用位置索引参数;也许这就是出问题的地方 - 也许是回溯。

代码：nodeT是trie节点，word是输入字符串，该函数是bool，如果字符串路径存在，则返回1/0。

bool Lexicon::containsWordHelper(nodeT *w, string word)) //check if prefix can be combined 
{ 
    if(word == "") { //base case: all char found 
     return true; 
    } else { 
     for(int i = 0; i < w->alpha.size(); i++) { //Loop through all of the children of the current node 
      if (w->alpha[i].letter == word[0]) 
       return containsWordHelper(w->alpha[i].next, word.substr(1)); 
      else if (word[0] == '0') //if '0' then step over and continue searching for valid path 
       containsWordHelper(w->alpha[i].next, word.substr(1)); //removed return here to allow looping through all the possible paths 
     } //I think it is continuing through after the loop and triggering return false 
    } 
    return false; //if char is missing - meaning the exact code is not there 
} 

问题是，当使用'0'通配符时，它返回false。这里出了什么问题？我的知识是有限的。

我在一段时间内攻击了这个问题，并使用'howboutthis howboutthat'方法，并发现将return放置在step over语句的结尾处。

bool Lexicon::containsWordHelper(nodeT *w, string word, int &time, int &wag, string compare) //check if prefix can be combined 
{ 
    if(word == "") { //base case: all letters found 
     if ((w->begin-wag) <= time && time <= (w->end+wag)) 
      return w->isWord; // case 2: timecard check for high/low date range 
     else if (time == ConvertDateToEpoch(9999, 01, 01)) return w->isWord; //this is for single code lookup w/o date 
    } else { 
     for(int i = 0; i < w->alpha.size(); i++) { //Loop through all of the children of the current node 
      if (w->alpha[i].letter == word[0]) 
       return containsWordHelper(w->alpha[i].next, word.substr(1), time, wag, compare); 
      else if (word[0] == 'ž') 
       if (containsWordHelper(w->alpha[i].next, word.substr(1), time, wag, compare)) return true; 
     } 
    } 
    return false; //if char is missing - meaning the exact code is not there 
} 

这似乎是合乎逻辑，如果我只有一个真正的结束返回然后递归完成且仅当为true，则有条件地传回后，我应该把返回的路径。它很有效，而且在回顾过程中看起来合乎逻辑，但我对此的信心充其量只是粗略。

我仍然有同样的问题。什么是/出错了？

Answer 1

解决：地方后，如果包含递归调用

bool Lexicon::containsWordHelper(nodeT *w, string word) 
    { 
     if(word == "") return w->isWord; 
     else { 
      for(int i = 0; i < w->alpha.size(); i++) { 
       if (w->alpha[i].letter == word[0]) 
        return containsWordHelper(w->alpha[i].next, word.substr(1)); 
       else if (word[0] == 'ž') 
        if (containsWordHelper(w->alpha[i].next, word.substr(1))) return true; 
      } 
     } 
     return false; 
    } 

Answer 2

您可以测试后者的结果containsWordHelper调用并返回true如果结果为true，否则继续迭代。