編寫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，否則繼續迭代。