在 Java 中实现 Trie

Question

我已经在 Java 中实现了 Trie 数据结构，但是当我在运行代码中时，我没有得到正确的答案。我使用一些简单的字符串构建了 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 来实现这个。

Answer 1

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 方法在线性时间内工作，因此将字符串添加到 trie 需要二次时间。您可以通过迭代单词的所有字符而不是对其子字符串进行递归来解决这个问题。消除递归也是一个好主意，因为对于较长的字符串，您可以运行进入堆栈溢出错误。

在 Java 中实现 Trie

Implementing a Trie in Java

java

algorithm

trie