用节点遍历编写trie解析递归函数

目的:此函数解析字符串trie,该字符串trie遵循与输入字符串匹配的路径。当解析字符串中的所有字符时, true 返回。如果仍然有有效的路径,我想跳过一个字符并返回。

应用程序:字符串是公路项目的位置层次结构。因此,项目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。这里出了什么问题?我的知识有限。

我破解了这个问题一段时间,并使用了“howbouthis-howbouthis”方法,发现 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结尾的路径返回,那么我应该在递归完成后放置返回,然后只有在true的情况下才有条件地返回。回想起来,这是可行的,似乎是合乎逻辑的,但我对此的信心充其量只是粗略的。

我仍然有同样的问题。出了什么问题?