我在理解trie的概念方面遇到了困难。从维基百科的“trie”词条中,我得到了这张图片:
如果我理解正确的话,在trie中,所有叶子节点都包含完整的单词拼写,而所有父节点则包含通向最终叶子节点的字符。所以,如果我定义了一个名为DigitalTreeNode的类,那么它应该是:
public class DigitalTreeNode {
public boolean isAWord;
public String wordToHere; (compiles all the characters in a word together)
public Map<String, DTN> children;
}
如果我想实现一个返回trie树中最长单词的方法,是否只需要在每个叶节点找到最长的单词?如何实现这样的方法:
```java public String findLongestWord() { // implementation goes here } ```
public static String longestWord (DigitalTreeNode d);
我猜测它涉及设置一个最长的字符串变量,递归地遍历每个节点并检查它是否是一个单词,如果它是一个单词并且它的长度大于最长变量,则最长变量=新单词长度。但是,我不确定Map子元素如何适合其中。使用上述方法如何找到任何trie中最长的单词?
O(|S|*n)
的时间内轻松找到它,其中|S|是平均字符串长度。我认为使用标准trie树无法更好地完成此任务,但如果你能操作数据结构,可能会有更好的方法。 - amit