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

痛定思痛。 2022-06-08 09:24 171阅读 0赞

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) 字典树的构造][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(){};
    }

[leetcode 208. Implement Trie _Prefix Tree_]: http://blog.csdn.net/jackzhang_123/article/details/78048320