Trie (Java) - ShuweiLeung/Thinking GitHub Wiki

1.（208:Medium）（非常非常经典题）Implement Trie (Prefix Tree)

• 前缀树（字典树）是一个非常经典的数据结构，该题考察建造前缀树，在实现过程中，我们将结点定义为含有val,isWord,childern的类，其中val是节点的值，isWord标记从根到当前结点的路径是否能构成单词，children是长度为26的节点类数组。根节点是一个没有val值，只起到索引导向的空值结点。具体实现看下边的代码：

class TrieNode {
    public char val;
    public boolean isWord; 
    public TrieNode[] children = new TrieNode[26];
    public TrieNode() {}
    TrieNode(char c){
        TrieNode node = new TrieNode();
        node.val = c;
    }
}

public class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
        root.val = ' ';
    }

    public void insert(String word) {
        TrieNode ws = root;
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(ws.children[c - 'a'] == null){
                ws.children[c - 'a'] = new TrieNode(c);
            }
            ws = ws.children[c - 'a'];
        }
        ws.isWord = true;
    }

    public boolean search(String word) {
        TrieNode ws = root; 
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(ws.children[c - 'a'] == null) return false;
            ws = ws.children[c - 'a'];
        }
        return ws.isWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode ws = root; 
        for(int i = 0; i < prefix.length(); i++){
            char c = prefix.charAt(i);
            if(ws.children[c - 'a'] == null) return false;
            ws = ws.children[c - 'a'];
        }
        return true;
    }
}

2.（677:Medium）（非常非常经典题）Map Sum Pairs

• insert()用来构建线段树，sum()先找到前缀，然后用DFS求和。具体代码参考如下：

    //利用segment tree
    class TrieNode {
        Map<Character, TrieNode> children;
        boolean isWord;
        int value;

        public TrieNode() {
            children = new HashMap<Character, TrieNode>();
            isWord = false;
            value = 0;
        }
    }
    
    TrieNode root;
    
    /** Initialize your data structure here. */
    public MapSum() {
        root = new TrieNode();
    }
    
    public void insert(String key, int val) {
        TrieNode curr = root;
        for (char c : key.toCharArray()) {
            TrieNode next = curr.children.get(c);
            if (next == null) {
                next = new TrieNode();
                curr.children.put(c, next);
            }
            curr = next;
        }
        curr.isWord = true;
        curr.value = val;
    }
    
    public int sum(String prefix) {
        TrieNode curr = root;
	for (char c : prefix.toCharArray()) {
	    TrieNode next = curr.children.get(c);
	    if (next == null) {
	        return 0;
	    }
	    curr = next;
        }
		
        return dfs(curr);
    }
    
    private int dfs(TrieNode root) {
        int sum = 0;
        for (char c : root.children.keySet()) {
            sum += dfs(root.children.get(c));
        }
        return sum + root.value;
    }

3.（1032:Hard）（非常非常经典题）Stream of Characters

• 该题的关键是反向建立字典树，因为query的过程是需要考虑前面的历史记录的。

    class TrieNode {
        boolean isWord;
        TrieNode[] next = new TrieNode[26];
    }

    TrieNode root = new TrieNode();
    StringBuilder sb = new StringBuilder(); //存储所有query的历史记录

    public _1032_StreamOfCharacters(String[] words) {
        createTrie(words);
    }

    public boolean query(char letter) {
        sb.append(letter); //注意query的时候，是连同前面所有的字符拼接在一起，一起进行单词的查找
        TrieNode node = root;
        for (int i = sb.length() - 1; i >= 0 && node != null; i--) {
            char c = sb.charAt(i);
            node = node.next[c - 'a'];
            if (node != null && node.isWord) {
                return true;
            }
        }
        return false;
    }

    private void createTrie(String[] words) {
        for (String s : words) {
            TrieNode node = root;
            int len = s.length();
            for (int i = len - 1; i >= 0; i--) { //我们反向建树，因为在query的时候，我们是query最前面的k个有效字符，k是有效单词的长度
                char c = s.charAt(i);
                if (node.next[c - 'a'] == null) {
                    node.next[c - 'a'] = new TrieNode();
                }
                node = node.next[c - 'a'];
            }
            node.isWord = true;
        }
    }