0

我有一种方法可以在前缀树中找到所有可能的单词。它接收一个节点并找到该节点的所有可能单词。但是，我需要它能够接受节点组合并找到组合的可能单词。该方法将搜索填充了单词字典的 trie。例如，与其从一个带有前缀“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];  
    }  
}
4

2 回答 2

2

我不太明白你的问题，但你所做的似乎首先是错误的，因为一旦你输出换行符，你就会丢失搜索路径的完整前缀。您可能应该更改 to 的签名，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)

于 2013-04-30T12:45:28.800 回答
1

这对你有用吗？作为 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;
}
于 2013-04-30T12:42:34.683 回答