如何找到一個trie中最長的單詞？

我無法理解trie的概念。從「特里」維基百科條目我看到這樣的畫面： enter image description here 如何找到一個trie中最長的單詞？

如果我看到這個正確的，在特里的所有葉子節點將會在整個單詞拼寫和所有的父節點保持領先了最後葉人物節點。所以，如果我已經

public class DigitalTreeNode { 
     public boolean isAWord; 
     public String wordToHere; (compiles all the characters in a word together) 
     public Map<String, DTN> children; 
}

如果我要實現它返回線索中最長的單詞將它僅僅涉及在每個葉子節點找到最長的單詞的方法定義了一個名爲DigitalTreeNode類？我將如何實現的方法，如：

public static String longestWord (DigitalTreeNode d);

我猜它必須設置一個最長的字符串變量，遞歸地通過每個節點會，並檢查它是否是一個字，如果它是一個詞，它的長度大於最長變量then最長= newWordLength。但是，我不確定Map兒童是如何適應的。我如何使用上述方法找到任何字符串中最長的單詞？

來源

2012-11-02 user1766888

什麼複雜性你在找什麼？關於結構的[BFS]（http://en.wikipedia.org/wiki/Breadth-first_search）可以很容易地在'O（| S | * n）'中找到它，其中| S |是平均字符串的長度。我認爲用標準的trie可以做得更好，但是如果你可以操縱DS，那麼我可以做得更好。 – amit

查看每個字符串字符並假設它們是| S |字符長，我認爲我可以做得比O（| S | * n）複雜得多。 – user1766888

葉節點通常不包含整個字符串（儘管它們可以），在樹狀結構中很多時候，葉節點只包含'$'符號來表示這是字符串的結尾。

要查找樹中最長的單詞，您可以在樹上使用BFS，首先找到「最後」樹葉。「最後一頁」是從BFS隊列中彈出的最後一個元素（在彈出BFS算法的空隊列停止之後）。
爲了從這片葉子得到真正的單詞，你需要從葉子上回到根部。 This thread討論瞭如何完成。

此解決方案是O(|S| * n)，其中|S|是字符串的平均長度，而n是DS中的字符串數。

如果你可以操縱線索DS，我認爲這是可以做到更好的（但它似乎並沒有在這個問題上的問題）

僞代碼：

findLongest(trie): 
    //first do a BFS and find the "last node" 
    queue <- [] 
    queue.add(trie.root) 
    last <- nil 
    map <- empty map 
    while (not queue.empty()): 
    curr <- queue.pop() 
    for each son of curr: 
     queue.add(son) 
     map.put(son,curr) //marking curr as the parent of son 
    last <- curr 
    //in here, last indicate the leaf of the longest word 
    //Now, go up the trie and find the actual path/string 
    curr <- last 
    str = "" 
    while (curr != nil): 
     str = curr + str //we go from end to start 
     curr = map.get(curr) 
    return str

來源

2012-11-02 08:53:16 amit

如何找到一個trie中最長的單詞？

回答

相關問題