如何獲取所有可能的單詞？

Question

我有一種方法可以查找前綴樹中所有可能的單詞。它接受一個節點併爲該節點找到所有可能的單詞。 但是，我需要它能夠接受節點的組合並找到可能的單詞組合。 該方法將搜索樹中，該樹填充了單詞詞典。 例如，如果從一個字母中找到所有可能的單詞，並且前綴'a'，它可以從前綴'ab'或'abo'中找到所有可能的單詞。 我只是不知道如何使用節點組合而不是僅從一個節點進行搜索。

public void findWords(Node node) { 

    if(node == null) return; 

    //searches through the branches of the node 
    // R is 26(the branches from each node on the trie) 
    // each one being a letter of the alphabet. 


    for(int i = 0; i < R; i++) { 
     if(node.next[i] != null) { 
      //printing each character 
      System.out.print((char) (97 + i)); 

      //identifying letter combo     
      if(node.next[i].isWord == true) { 

       System.out.println(); 

      } 
      //back into the loop 
      findWords(node.next[i]); 
     } 

    } 
} 

節點類：

public class TextPredictTrie { 

private final int R = 26; // the trie branches 
private Node root = new Node(); // the root node 

// the t9 mapped array which maps number to string on the typing board 
private String[] t9 = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 

// trie node definition 
private class Node { 
    private boolean isWord; 
    private Node[] next; 

    public Node() { 
     this(false); 
    } 

    public Node(boolean isWord) { 
     this.isWord = isWord; 
     this.next = new Node[R]; 
    } 
} 

Answer 1

我真的不明白你的問題，但你在做什麼似乎是錯擺在首位，因爲一旦你輸出一個換行符，你失去了你的搜索路徑的完整前綴。您可能應該將findWords(Node node)的簽名更改爲findWords(String prefix, Node node)，以維護前綴。我還建議對該方法進行輕微重組：

public void findWords(String prefix, Node node) { 

    if(node == null) return; 

    if(node.isWord) // Check here 
     System.out.println(prefix); 

    //searches through the branches of the node 
    // R is 26(the branches from each node on the trie) 
    // each one being a letter of the alphabet. 
    for(int i = 0; i < R; i++) { 
     if(node.next[i] != null) { 
      // append next character to prefix 
      findWords(prefix + ('a' + i), node.next[i]); 
     } 
    } 
} 

不用說，這是非常低效的。您可能想要查看遞歸調用返回時的StringBuilder類，遞歸前的append(char)和removeCharAt(length-1)。

Answer 2

將這項工作嗎？作爲Node的一種方法。

public List<String> findWords() { 

    List<String> result = new ArrayList<String>(); 

    if(this.isWord) 
     result.add(""); 

    for(int i = 0; i < R; i++) 
     if(next[i] != null){ 
      List<String> childResult = next[i].findWords(); 
      char letter = (char) (97 + i); 
      for(String sufix : childResult) 
       result.add("" + letter + sufix); 
     } 
    return result; 
}