Add and Search Word 473

Question

Design a data structure that supports the following two operations: addWord(word) and 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.

Notice

You may assume that all words are consist of lowercase letters a-z.

Example

addWord("bad")

addWord("dad")

addWord("mad")

search("pad") // return false

search("bad") // return true

search(".ad") // return true

search("b..") // return true

Solution

1) 创建标准的TrieNode

2) addWord(): 和标准的Trie的insert()相同

3) search(): 本来只要依次比较now.subTree中是否含有当前字符，但是因为输入字符串中可能含有'.'(代表任意字符)，所以在遇到'.'时，需要查看now.subTree中包含的所有可能字符，即要查看从now这个点之后所有分岔路径是否能组成输入字符串。因此，迭代的方法不行，需要使用递归的方法。

递归检查当前节点now的subtree是否包含当前位置的字符，若包含则递归检查下一位置字符；若不包含，则看当前位置的字符是否为'.'，若不是则返回false，若是则依次递归检查当前节点now的subtree中包含的所有节点和下一位置字符，只要subtree中有一个返回true则返回true，否则返回false。

当检查字符串最后一个位置时，递归到底。此时若最后一位字符为'.'，则只要now的subtree中包含任意叶节点，即返回true，否则返回false。若最后一位字符不为'.'，若now的subtree包含该字符且该字符的节点为叶节点时，返回true，否则返回false。

代码如下：

class TrieNode{
    String s;
    boolean isString;
    HashMap<Character, TrieNode> subTree;
    public TrieNode(){
        s = "";
        isString = false;
        subTree = new HashMap<Character, TrieNode>();
    }
}

public class WordDictionary {
    TrieNode root = new TrieNode();
    // Adds a word into the data structure.
    public void addWord(String word) {
        // Write your code here
        if(word == null){
            return;
        }

        TrieNode now = root;
        for(int i = 0; i < word.length(); i++){
            if(!now.subTree.containsKey(word.charAt(i))){
                now.subTree.put(word.charAt(i), new TrieNode());
            }
            now = now.subTree.get(word.charAt(i));
        }
        now.s = word;
        now.isString = 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) {
        // Write your code here
        if(word == null){
            return true;
        }

        TrieNode now = root;
        return helper(now, word, 0);
    }

    private boolean helper(TrieNode now, String word, int pos){
        //递归到底时，若最后一位字符为'.'，则只要now的subtree中包含任意叶节点，即返回true，否则返回false
        if(pos == word.length() - 1){
            if(word.charAt(pos) == '.'){
                for(char c : now.subTree.keySet()){
                    TrieNode next = now.subTree.get(c);
                    if(next.isString){
                        return true;
                    }
                }
                return false;
            }

            //若最后一位字符不为'.'，若now的subtree包含该字符且该字符的节点为叶节点时，返回true，否则返回false
            if(now.subTree.containsKey(word.charAt(pos)) && now.subTree.get(word.charAt(pos)).isString){
                return true;
            }

            return false;
        }
        //递归检查当前节点now的subtree是否包含当前位置的字符，若包含则递归检查下一位置字符
        if(now.subTree.containsKey(word.charAt(pos))){
            return helper(now.subTree.get(word.charAt(pos)), word, pos + 1);
        }else{
        //若不包含，则看当前位置的字符是否为'.'，若是则依次递归检查当前节点now的subtree中包含的所有节点和下一位置字符，只要subtree中有一个返回true则返回true，否则返回false
            if(word.charAt(pos) == '.'){
                ArrayList<Boolean> hasString = new ArrayList<Boolean>();
                for(char c : now.subTree.keySet()){
                    TrieNode next = now.subTree.get(c);
                    hasString.add(helper(next, word, pos + 1));
                }
                for(boolean b : hasString){
                    if(b){
                        return true;
                    }
                }
                return false;
            }

            return false;
        }
    }
}

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary = new WordDictionary();
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");