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

Note:

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

You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.

Tips:

O(n)

先建立trie tree， 然后用BFS搜索。需要注意的是

1. trie树中isKey代表是不是单词的结束。
2. 碰到‘.‘要把当前层不是null的全部加入queue再搜索。

Code:

public class WordDictionary {
    class TrieNode {
        boolean isKey;
        TrieNode[] children;
        public TrieNode() {
            children = new TrieNode[26];
            for (int i = 0; i < 26; i++) {
                children[i] = null;
            }
        }
    }
    TrieNode root = new TrieNode();
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode copy = root;
        for (char c : word.toCharArray()) {
            if (copy.children[c - 'a'] == null) {
                copy.children[c - 'a'] = new TrieNode();
            }
            copy = copy.children[c - 'a'];
        }
        copy.isKey = 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 dfs(word, 0, root);
    }

    private boolean dfs(String word, int depth, TrieNode node) {
        if (depth == word.length()) {
            return node.isKey;
        }
        char c = word.charAt(depth);
        if (c != '.') {
            return node.children[c - 'a'] != null && dfs(word, depth + 1, node.children[c - 'a']);
        } else {
            for (TrieNode child : node.children) {
                if (child != null) {
                    if (dfs(word, depth + 1, child)) {
                        return true;
                    }
                }
            }
            return false;
        }
    }
}

bfs

public class WordDictionary {

    class TrieNode {
        boolean isKey;
        TrieNode[] children;
        public TrieNode() {
            isKey = false;
            children = new TrieNode[26];
            for (int i = 0; i < 26; i++) {
                children[i] = null;
            }
        }
    }
    private TrieNode root;

    public WordDictionary() {
        root = new TrieNode(); 
    }
    // Adds a word into the data structure.
    public void addWord(String word) {
        TrieNode copy = root;
        for (int i = 0; i < word.length(); i++) {
            if (copy.children[word.charAt(i) - 'a'] == null) {
                copy.children[word.charAt(i) - 'a'] = new TrieNode();
                copy = copy.children[word.charAt(i) - 'a'];
            }
            else copy = copy.children[word.charAt(i) - 'a'];
        }
        copy.isKey = 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) {
        Queue<TrieNode> queue = new LinkedList<>();
        queue.offer(root);
        for (int i = 0; i < word.length(); i++) {
            if (word.charAt(i) == '.') {
                int size = queue.size();
                if (size == 0) {
                    return false;
                }
                for (int j = 0; j < size; j++) {
                    TrieNode current = queue.poll();
                    for (int x = 0; x < 26; x++) {
                        if (current.children[x] != null) {
                            queue.offer(current.children[x]);
                        }
                    }
                }
            }
            else {
                int size = queue.size();
                if (size == 0) {
                    return false;
                }
                for (int j = 0; j < size; j++) {
                    TrieNode current = queue.poll();
                    if (current.children[word.charAt(i) - 'a'] != null) {
                        queue.offer(current.children[word.charAt(i) - 'a']);
                    }
                }
            }
        }
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TrieNode current = queue.poll();
            if (current.isKey) {
                return true;
            }
        }
        return false;
    }

}