208. 实现 Trie (前缀树)

approach 1

class Trie {
    Trie[] next = new Trie[26];
    boolean end = false;
    public Trie() {
    }
    
    public void insert(String word) {
        char[] cs = word.toCharArray();
        Trie nx = this;
        for (char c : cs) {
            if (nx.next[c-'a'] == null) {
                nx.next[c-'a'] = new Trie();
            }
            nx = nx.next[c-'a'];
        }
        nx.end = true;
    }
    
    public boolean search(String word) {
        char[] cs = word.toCharArray();
        Trie nx = this;
        for (char c : cs) {
            if (nx.next[c-'a'] == null) {
                return false;
            }
            nx = nx.next[c-'a'];
        }
        return nx.end;
    }
    
    public boolean startsWith(String prefix) {
        char[] cs = prefix.toCharArray();
        Trie nx = this;
        for (char c : cs) {
            if (nx.next[c-'a'] == null) {
                return false;
            }
            nx = nx.next[c-'a'];
        }
        return true;
    }
}

approach 2，数组构造

class Trie {
    // 直接设置为十万级
    int N = 100009;
    // 用该二维数组存储所有的单词字符
    int[][] trie;
    // 记录某个单词结尾的次数
    int[] count;
    // index自增来记录用了多少格子
    int index;

    public Trie() {
        trie = new int[N][26];
        count = new int[N];
        index = 0;
    }
    
    public void insert(String word) {
        int pos = 0;
        for (int i = 0; i < word.length(); i++) {
            int c = (int) (word.charAt(i)-'a');
            if (trie[pos][c] == 0) {
                trie[pos][c] = ++index;                
            }
            pos = trie[pos][c];
        }
        count[pos]++;
    }
    
    public boolean search(String word) {
        int pos = 0;
        for (int i = 0; i < word.length(); i++) {
            int c = (int) (word.charAt(i)-'a');
            if (trie[pos][c] == 0) {
                return false;
            }
            pos = trie[pos][c];
        }
        return count[pos] != 0;
    }
    
    public boolean startsWith(String prefix) {
        int pos = 0;
        for (int i = 0; i < prefix.length(); i++) {
            int c = (int) (prefix.charAt(i)-'a');
            if (trie[pos][c] == 0) {
                return false;
            }
            pos = trie[pos][c];
        }
        return true;
    }
}