使用递归在数字树中查找最长的单词

Question

我有一个简单的数字树，定义如下：

class DTN {
  public:
    DTN () :
      is_word(false), word_to_here(""), children()
    {}
    DTN (bool iw, std::string wth) :
      is_word(iw), word_to_here(wth), children()
    {}
    bool                     is_word;
    std::string              word_to_here;
    Map<char,DTN>  children;
};

我在定义一个名为longest_word (const DTN& dtn)的函数时遇到了问题，该函数假定使用迭代器和递归返回数字树中最长的单词，如下所示：

std::string longest_word (const DTN& dtn) {
    std::string lw = dtn.word_to_here;
    for(auto s:dtn.children){
        if(s.second.is_word && lw.length()<s.second.word_to_here.length()){
            lw = longest_word(s.second);
        }
        longest_word(s.second);
    }
    return lw;
}

假设我们在数字树DTN中有三个单词：(ante，anteater，anthebellum)，调用longest_word(DTN)会得到一个空字符串"“而不是"anthebellum”。有人能指出我在longest_word函数中做错了什么吗？有实际的代码将被欣赏，因为我的英语不是很好，代码对我来说更容易理解。提前谢谢。

Answer 1

longest_word的算法是完全错误的。您应该检查所有的子longest_words，并返回较长的那个。在对子对象的循环完成之前，您不能返回。请注意，您的算法将始终在第一个子对象上返回。我甚至不明白你为什么要在那里检查一个完整的单词。

我可以试着写正确的代码，但我觉得它对你没有用。我的建议是回到最简单的算法，比如在整数列表中寻找最大数。