[LeetCode-JAVA] Add and Search Word - Data structure design

浏览数：454 / 时间：2015年06月08日

题目：

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
Note:
You may assume that all words are consist of lowercase letters a-z.

思路：刚做完前序树的题，正好拿来用，建立的时候完全一样，搜索的时候因为要对‘.‘进行判断因此要循环所有孩子的可能，将for循环拆成每个字符判定一次的搜索。

代码：

class TrieNode{
    boolean isWord;
    Map<Character, TrieNode> nexts;
    public TrieNode(){
        nexts = new HashMap<Character, TrieNode>();
    }
}
public class WordDictionary {
    TrieNode root = new TrieNode();
    // Adds a word into the data structure.
    public void addWord(String word) {
        char[] toArray = word.toCharArray();
        TrieNode temp = root;
        for(int i = 0 ; i < toArray.length ; i++){
            if(!temp.nexts.containsKey(toArray[i])){
                temp.nexts.put(toArray[i], new TrieNode());
            }
            temp = temp.nexts.get(toArray[i]);
            if(i == toArray.length-1)
                temp.isWord = 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 singleSearch(word, root);
    }
    public boolean singleSearch(String word, TrieNode head){
        if(head==null) return false;
        if(word.length() == 0 ) return head.isWord;
          
        Map<Character, TrieNode> children = head.nexts;
        char c = word.charAt(0);
        
        if(c==‘.‘) {
            for(char key : children.keySet()){  //判断所有孩子的可能
                if(singleSearch(word.substring(1), children.get(key) )) return true;  
            }  
            return false;  
        }
        if(children.containsKey(c)){  //进行下一个字符的判断
            return singleSearch(word.substring(1), children.get(c));
        }else
            return false;
    }
}