Add and Search Word - Data structure design(Medium)

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

解题思路:Trie+DFS

public class WordDictionary {

    // Adds a word into the data structure.
    Trier root = new Trier();
    public void addWord(String word) {
        Trier pointer = root;
        for(int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (pointer.children[c-'a'] == null) {
                pointer.children[c-'a'] = new Trier();
                pointer = pointer.children[c-'a'];
            } else {
                pointer = pointer.children[c-'a'];
            }
        }
        pointer.flag = 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) {
        Trier pointer = root;
        return helper(word,0,pointer);
    }
    private boolean helper(String word, int start, Trier cur) {
        if (start == word.length()) {
            if (cur.flag) {
                return true;
            } else {
                return false;
            }
        }
        char c = word.charAt(start);
        if (c == '.') {
            for (int i = 0; i < 26; i++) {
                if (cur.children[i] != null) {
                    if (helper(word,start+1,cur.children[i])) {
                        return true;
                    }
                }
            }
        } else {
            if (cur.children[c-'a'] == null) {
                return false;
            } else {
                return helper(word,start+1,cur.children[c-'a']);
            }
        }
        return false;
    }
    class Trier {
        Trier[] children;
        char c;
        boolean flag;
        public Trier() {
            children = new Trier[26];
            flag = false;
        }
    }
}