力扣

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.

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.

public class WordDictionary {
    WordNode root = new WordNode();
    public void addWord(String word) {
        char chars[] = word.toCharArray();
        addWord(chars, 0, root);
    }
    
    private void addWord(char[] chars, int index, WordNode parent) {
        char c = chars[index];
        int idx = c-'a';
        WordNode node = parent.children[idx];
        if (node == null){
            node = new WordNode();
            parent.children[idx]=node;
        }
        if (chars.length == index+1){
            node.isLeaf=true;
            return;
        }
        addWord(chars, ++index, node);
    }


    public boolean search(String word) {
        return search(word.toCharArray(), 0, root);                  
    }
    
    private boolean search(char[] chars, int index, WordNode parent){
        if (index == chars.length){
            if (parent.isLeaf){
                return true;
            }
            return false;
        }
        WordNode[] childNodes = parent.children;
        char c = chars[index];
        if (c == '.'){
            for (int i=0;i<childNodes.length;i++){
                WordNode n = childNodes[i];
                if (n !=null){
                    boolean b = search(chars, index+1, n);
                    if (b){
                        return true;
                    }
                }
            }
            return false;
        }
        WordNode node = childNodes[c-'a'];
        if (node == null){
            return false;
        }
        return search(chars, ++index, node);
    }
    

    
    private class WordNode{
        boolean isLeaf;
        WordNode[] children = new WordNode[26];
    }
}