208. 实现 Trie (前缀树)

Problem: 208. 实现 Trie (前缀树)

字典树概念

首先，Trie树，也叫字典树或者前缀树，基础的应用就是可以用来检索字符串或者字符串前缀。为了实现这个功能，树上从根节点到叶子节点的路径定义为一个存储的字符串。这也提供了树状存储的一个新思路，除了用来维护子节点和父节点的关系，运用分治思想外，树状存储也可以利用路径信息。

原先做法

class Trie {
    public Node root;
    public Trie() {
        root = new Node();
    }
    
    public void insert(String word) {
        char cs[] = word.toCharArray();
        int index = 0;
        Node p = root;
        while (index < word.length()) {
            boolean find = false;
            for (Node n: p.sub) {
                if (n.val == cs[index]) {
                    p = n;
                    index++;
                    find = true;
                    if (index == word.length()) p.end = true;
                    break;
                }
            }
            if (find) continue;
            while(index < cs.length) {
                Node next = new Node(cs[index]);
                p.sub.add(next);
                p = next;
                index++;
                if (index == word.length()) p.end = true;
            }
            break;
        }
    }
    
    public boolean search(String word) {
        Node p = root;
        for (int i = 0; i < word.length(); i++) {
            boolean find = false;
            for (Node n : p.sub) {
                if (n.val == word.charAt(i)) {
                    find = true;
                    p = n;
                    break;
                }
            }
            if (!find) return false;
        }
        if (p.end == false) return false;
        return true;
    }
    
    public boolean startsWith(String prefix) {
        Node p = root;
        for (int i = 0; i < prefix.length(); i++) {
            boolean find = false;
            for (Node n : p.sub) {
                if (n.val == prefix.charAt(i)) {
                    find = true;
                    p = n;
                    break;
                }
            }
            if (!find) return false;
        }
        return true;
    }
}

做法改进

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

首先这个写法有时空效率上的改进。因为题目限定了给定词汇只由小写字母构成，而小写字母是连续的，我们可以直接用一个定长数组来表示26个字母，而不必开一个子列表。通过列表哈希可以减少查询时的一层for循环遍历。

另外，我的插入写法也存在问题，其实并不需要一个flag来标志，只需要每次在不存在该字符的时候插入即可，不需要分两段进行。