Design a data structure that supports the following two operations:addWord(word)andsearch(word)

search(word)can search a literal word or a regular expression string containing only lettersa-zor..

A.means it can represent any one letter.

Notice

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

Have you met this question in a real interview?

Yes

Example

addWord("bad")
addWord("dad")
addWord("mad")
search("pad")  // return false
search("bad")  // return true
search(".ad")  // return true
search("b..")  // return true

1. hashmap + dfs

class TrieNode {
    boolean hasWord;
    HashMap<Character, TrieNode> children = null;
    public TrieNode() {
        children = new HashMap<Character, TrieNode>();
        hasWord = false;
    }
}
public class WordDictionary {
    /*
     * @param word: Adds a word into the data structure.
     * @return: nothing
     */
    private TrieNode root = new TrieNode();
    public void addWord(String word) {
        // write your code here
        TrieNode cur = root;
        char[] wordArray = word.toCharArray();
        for (int i = 0; i < wordArray.length; i++) {
            if (!cur.children.containsKey(wordArray[i])) {
                cur.children.put(wordArray[i], new TrieNode());
            }
            cur = cur.children.get(wordArray[i]);
        }
        cur.hasWord = true;

    }

    /*
     * @param word: A word could contain the dot character '.' to represent any one letter.
     * @return: if the word is in the data structure.
     */
    public boolean search(String word) {
        // write your code here
        return dfs(root, word, 0);
    }


    public boolean dfs(TrieNode root, String word, int index) {
        if (word.length() == index) {
            return root.hasWord;
        }
        if (root.children.size() == 0) {
            return false;
        }

        if (root.children.containsKey(word.charAt(index))) {
            if ((word.length() - 1) == index) {
                return root.children.get(word.charAt(index)).hasWord;
            }
            return dfs(root.children.get(word.charAt(index)), word, index + 1);
        }

        if (word.charAt(index) == '.') {

            if ((word.length() - 1) == index) {
                for (TrieNode cur : root.children.values()) {
                    if (cur.hasWord) {
                        return true;
                    }
                }
            } else {
                for (TrieNode cur : root.children.values()) {
                    if (dfs(cur, word, index + 1)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }
}

2.hashmap + bfs 分层bfs, 如果遇到 '.' 则需要把该所有的children都加入队列， 否则只将该层符合字符的结点加入队列

class TrieNode {
    boolean hasWord;
    HashMap<Character, TrieNode> children = null;
    public TrieNode() {
        children = new HashMap<Character, TrieNode>();
        hasWord = false;
    }
}
public class WordDictionary {
    /*
     * @param word: Adds a word into the data structure.
     * @return: nothing
     */
    private TrieNode root = new TrieNode();
    public void addWord(String word) {
        // write your code here
        TrieNode cur = root;
        char[] wordArray = word.toCharArray();
        for (int i = 0; i < wordArray.length; i++) {
            if (!cur.children.containsKey(wordArray[i])) {
                cur.children.put(wordArray[i], new TrieNode());
            }
            cur = cur.children.get(wordArray[i]);
        }
        cur.hasWord = true;

    }

    /*
     * @param word: A word could contain the dot character '.' to represent any one letter.
     * @return: if the word is in the data structure.
     */
    public boolean search(String word) {
        // write your code here
        Queue<TrieNode> queue = new LinkedList<TrieNode>();
        TrieNode cur = root;
        queue.offer(cur);

        int i = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            boolean flag = false;
            for (int k = 0; k < size; k++) {
                TrieNode current = queue.poll();

                if (current.children.containsKey(word.charAt(i))) {
                    queue.offer(current.children.get(word.charAt(i)));
                    flag |= current.children.get(word.charAt(i)).hasWord;
                } else if (word.charAt(i) == '.') {
                    for (TrieNode trie : current.children.values()) {
                        queue.offer(trie);
                        flag |= trie.hasWord;
                    }
                }
            }
            i++;
            if (i >= word.length()) {
                return flag;
            }
        }
        return false;
    }
}