在Java中实现Trie

我在Java中实现了Trie数据结构，但在运行代码时没有得到正确的答案。我使用一些简单的字符串构建了trie。然后我搜索单词和前缀，但结果不正确。我试过很多次，但仍然找不到可能出错的地方。在Java中实现Trie

Trie.java：

public class Trie { 

    public class Vertex { 
     public int words; 
     public int prefixes; 
     public Vertex edges[] = new Vertex[26]; 

     public Vertex() { 
      this.words = 0; 
      this.prefixes = 0; 
     } 
    } 

    private Vertex root; 

    Trie() { 
     this.root = new Vertex(); 
    } 

    private void addWord(Vertex vertex, String word) { 
     if (word.isEmpty()) { 
      vertex.words++; 
     } else { 
      vertex.prefixes++; 
      int indexOfNextChar = (int) word.charAt(0) - 97; 
      vertex.edges[indexOfNextChar] = new Vertex(); 
      this.addWord(vertex.edges[indexOfNextChar], word.substring(1)); 
     } 
    } 

    private int countWords(Vertex vertex, String word) { 
     if (!word.isEmpty()) { 
      int indexOfNextChar = (int) word.charAt(0) - 97; 
      if (vertex.edges[indexOfNextChar] == null) { 
       return 0; 
      } else { 
       return this.countWords(vertex.edges[indexOfNextChar], word.substring(1)); 
      } 
     } else { 
      return vertex.words; 
     } 
    } 

    private int countPrefixes(Vertex vertex, String word) { 
     if (!word.isEmpty()) { 
      int indexOfNextChar = (int) word.charAt(0) - 97; 
      if (vertex.edges[indexOfNextChar] == null) { 
       return 0; 
      } else { 
       return this.countPrefixes(vertex.edges[indexOfNextChar], word.substring(1)); 
      } 
     } else { 
      return vertex.prefixes; 
     } 
    } 

    public void addWord(String word) { 
     this.addWord(this.root, word.toLowerCase()); 
    } 

    public int countPrefixes(String word) { 
     if (word.length() != 0) { 
      return this.countPrefixes(this.root, word.toLowerCase()); 
     } 
     return -1; 
    } 

    public int countWords(String word) { 
     if (word.length() != 0) { 
      return this.countWords(this.root, word.toLowerCase()); 
     } 
     return -1; 
    } 
}

TrieTester.java

public class TrieTester { 
    public static void main(String[] args) { 
     Trie trie = new Trie(); 
     trie.addWord("Ayush"); 
     trie.addWord("Ayur"); 
     trie.addWord("Ayub"); 
     trie.addWord("Ayan"); 
     trie.addWord("Bhushan"); 

     // Should output 0, outputs 0 
     System.out.println("Count of word Ayus: " + trie.countWords("Ayus")); 

     // Should output 1, outputs 0 
     System.out.println("Count of word Ayush: " + trie.countWords("Ayush")); 

     // Should output 4, outputs 1 
     System.err.println("Count of prefix Ay: " + trie.countPrefixes("Ay")); 
    } 
}

我提到的Topcoder Trie tutorial来实现这一点。

来源

2017-04-19 ayushgp

我开始测试1字符的字符串，然后是2个字符的字符串，并检查trie的完整状态。 – 9000

使用调试器逐步完成，并仔细观察边缘情况。尤其要注意当你创建一个新的顶点时，你需要在创建第一个顶点之后重用它们。 –

在addWord方法的else条款肯定是不正确的（有可能是其他错误，太）：

vertex.prefixes++; 
int indexOfNextChar = (int) word.charAt(0) - 97; 
vertex.edges[indexOfNextChar] = new Vertex(); 
this.addWord(vertex.edges[indexOfNextChar], word.substring(1));

你的代码总是创建一个新的顶点。这是错误的。当且仅当给定角色没有边缘时，你应该这样做。也就是说，它应该是这样的：

if (vertex.edges[indexOfNextChar] == null) { 
    vertex.edges[indexOfNextChar] = new Vertex(); 
}

您的实施还有一些其他问题。例如，String.substring方法在线性时间内工作，因此向树中添加字符串需要二次时间。您可以通过迭代单词的所有字符来修复该问题，而不是对其子字符串进行递归。消除递归也是一个好主意，因为对于较长的字符串可能会遇到堆栈溢出错误。

来源

2017-04-19 20:38:51 kraskevich

在Java中实现Trie

回答

相关问题