[LintCode] 442 Implement Trie 解题报告

Description
Implement a trie with insert, search, and startsWith methods.

Notice
You may assume that all inputs are consist of lowercase letters a-z.


Example
insert("lintcode")
search("code")
>>> false
startsWith("lint")
>>> true
startsWith("linterror")
>>> false
insert("linterror")
search("lintcode)
>>> true
startsWith("linterror")
>>> true


思路
这题主要是要细心。
insert的时候就是看下面能不能走。能走就直接走。不能走就做一个新的点。走到底以后记得把最后的节点标记一下结束。
startsWith的时候就看能不能走。不能走就直接false了。能走就接着走。走完返回true。
search和startsWith差不多，就是多一个判断，走完以后看一下最后这个点有没有标记过结束。



Code

/**
 * Your Trie object will be instantiated and called as such:
 * Trie trie = new Trie();
 * trie.insert("lintcode");
 * trie.search("lint"); will return false
 * trie.startsWith("lint"); will return true
 */
class TrieNode {
    // Initialize your data structure here.
    private int R = 26;
    public TrieNode[] next;
    public boolean isWordEnd;
    
    public TrieNode() {
        this.next = new TrieNode[R];
        for (int i = 0; i < R; i++) {
            this.next[i] = null;
        }
        this.isWordEnd = false;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        insertWord(root, word, 0);
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode res = findWord(root, word, 0);
        if (res == null) {
            return false;
        }
        return res.isWordEnd;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        return findWord(root, prefix, 0) != null;
    }
    
    public void insertWord(TrieNode root, String word, int pos) {
        
        if (pos == word.length()) {
            root.isWordEnd = true;
            return;
        }
        
        char c = word.charAt(pos);
        if (root.next[c - 'a'] == null) {
            root.next[c - 'a'] = new TrieNode();
        }
        root = root.next[c - 'a'];
        insertWord(root, word, pos + 1);
    }
    
    public TrieNode findWord(TrieNode root, String word, int pos) {
        if (pos == word.length()) {
            return root;
        }
        
        char c = word.charAt(pos);
        if (root.next[c - 'a'] == null) {
            return null;
        }
        root = root.next[c - 'a'];
        return findWord(root, word, pos + 1);
    }
}