211. Add and Search Word - Data structure design-蒲公英云

211. Add and Search Word - Data structure design

Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
Example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.

本题与208. Implement Trie (Prefix Tree)类似，都是前缀树的应用。详细代码如下：

/**
 * 208. Implement Trie (Prefix Tree)
 * 前缀树的节点定义
 */
class TrieNode {
    private TrieNode[] links;//最多有26个子节点
    private final int MAX_NODE = 26;
    private boolean isEnd;//判断该节点是否是尾结点（即是否存在从根节点到该节点的单词）
    public TrieNode() {
        links = new TrieNode[MAX_NODE];
    }
    public boolean containsKey(char ch) {
        return links[ch-'a'] != null;
    }
    public TrieNode get(char ch) {
        return links[ch-'a'];
    }
    public void put(char ch, TrieNode node) {
        links[ch-'a'] = node;
    }
    public boolean isEnd() {
        return isEnd;
    }
    public void setEnd(boolean end) {
        isEnd = end;
    }
}
/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */
class WordDictionary {
    private TrieNode root;
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new TrieNode();
    }
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode node = root;
        for(int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);
            if(!node.containsKey(ch)) {
                node.put(ch, new TrieNode());
            }
            node = node.get(ch);
        }
        node.setEnd(true);
    }
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return searchFrom(word, root);
    }
    private boolean searchFrom(String word, TrieNode node) {
        if(node == null || word == null) return false;
        for(int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);
            if(ch != '.') {
                if(!node.containsKey(ch)) {
                    return false;
                }
                node = node.get(ch);
            } else {
                String sub = word.substring(i+1);
                for(char cc = 'a'; cc <= 'z'; ++cc) {
                    if(searchFrom(sub, node.get(cc)))
                        return true;
                }
                return false;
            }
        }
        return node != null && node.isEnd();
    }
}