leetcode 211. Add and Search Word - Data structure design 字典树的简单应用-蒲公英云

leetcode 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.

For example:

addWord(“bad”)
addWord(“dad”)
addWord(“mad”)
search(“pad”) -> false
search(“bad”) -> true
search(“.ad”) -> true
search(“b..”) -> true

这道题和leetcode 208. Implement Trie (Prefix Tree) 字典树的构造基本一样，不过在搜索的过程中使用了DFS深度优先遍历，字典树应该记住。

代码如下：

public class WordDictionary 
{
    private TrieNode root = new TrieNode();
    public void addWord(String word) 
    {
        Map<Character, TrieNode> children = root.children;
        for(int i=0; i<word.length(); i++)
        {
            char c = word.charAt(i);
            TrieNode t=null;
            if(children.containsKey(c))
                t = children.get(c);
            else 
            {
                t = new TrieNode(c);
                children.put(c, t);
            }
            children = t.children;
            if(i==word.length()-1)
                t.leaf=true;
        }
    }
    public boolean search(String word) 
    {
        return searchNode(word, root);
    }
    /*
     * 递归搜索
     * 
     * */
    public boolean searchNode(String word, TrieNode tn) 
    {
        if(tn==null) 
            return false;
        if(word.length() == 0 )
            return tn.leaf;
        Map<Character, TrieNode> children = tn.children;
        TrieNode t = null;
        char c = word.charAt(0);
        if(c=='.') 
        {
            for(char key : children.keySet() ) 
            {
                if(searchNode(word.substring(1), children.get(key) )) 
                    return true;
            }
            return false;
        } else if(!children.containsKey(c)) 
            return false;
        else 
        {
            t = children.get(c);
            return searchNode(word.substring(1), t);
        }
    }    
}
class TrieNode 
{
    // Initialize your data structure here.
    char c;
    boolean leaf;
    HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
    public TrieNode(char c) 
    {
        this.c = c;
    }    
    public TrieNode(){};
}