Add and Search Word

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.

思路：

　　前缀树+回溯

我的代码：

public class WordDictionary {

    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }
    public void addWord(String word) {
        HashMap<Character, TrieNode> children = root.children;
        for(int i=0; i<word.length(); i++)
        {
            TrieNode node;
            char c = word.charAt(i);
            if(children.containsKey(c)) node = children.get(c);
            else
            {
                node = new TrieNode(c);
                children.put(c,node);
            }
            children = node.children;
            if(i == word.length()-1)
            {
                node.isWord = true;
            }
        }
    }
    public boolean search(String word) {
        if(word==null || word.length()==0)    return true;
        HashMap<Character, TrieNode> children = root.children;
        return helperSearch(word, children);
        
    }
    public boolean helperSearch(String word, HashMap<Character, TrieNode> hash)
    {
        if(word.length() == 1)
        {
            char c = word.charAt(0);
            if(c == '.')
            {
                for(char key : hash.keySet())
                {
                    if(hash.get(key).isWord) return true;
                }
                return false;
            }
            else
            {
                if(hash.containsKey(c))        return hash.get(c).isWord;
                else return false;
            }
        }
        if(word.charAt(0) == '.')
        {
            for(char c: hash.keySet())
            {
                if(helperSearch(word.substring(1), hash.get(c).children))   return true;   
            }
            return false;
        }
        else
        {
            char c = word.charAt(0);
            if(hash.containsKey(c))
            {
                return helperSearch(word.substring(1), hash.get(c).children);
            }
            else return false;
        }
    }
    class TrieNode {
        public TrieNode() {
        }
        public TrieNode(char c) {
            this.c = c;
        }
        char c;
        HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();  
        boolean isWord;
    }
}

学习之处：

• 之前做了前缀树的解法，很自然的考虑到了回溯的解法，一遍AC了