Add and Search Word

Master this topic with zero to advance depth.

Add and Search Word

Design a data structure that supports adding new words and finding if a string matches any previously added string, including wildcard character '.' matching.

Medium

Examples

Input: addWord("bad"), addWord("dad"), search(".ad")
Output: true, true, true

Approach 1

Level III: Trie + DFS (Optimal)

Intuition

Standard Trie implementation. When encountering '.', perform DFS to check all possible children of the current node.

⏱ Add: O(L), Search: O(26^L) worst case.💾 O(N * L * 26).

Detailed Dry Run

Search '.ad': Root -> dfs('.'). Try 'a'-'z'. 'b' exists. From 'b', dfs('ad') -> matches 'ad' and isEnd=true. Return true.

java

class WordDictionary {
    class Node { Node[] children = new Node[26]; boolean isEnd = false; }
    Node root = new Node();
    public void addWord(String w) { Node c=root; for(char x:w.toCharArray()) { int i=x-'a'; if(c.children[i]==null) c.children[i]=new Node(); c=c.children[i]; } c.isEnd=true; }
    public boolean search(String w) { return dfs(w, 0, root); }
    private boolean dfs(String w, int i, Node n) {
        if(n==null) return false; if(i==w.length()) return n.isEnd;
        char x=w.charAt(i);
        if(x=='.') { for(Node child:n.children) if(dfs(w, i+1, child)) return true; return false; }
        return dfs(w, i+1, n.children[x-'a']);
    }
}

← Previous QuestionImplement Trie (Prefix Tree)

Next Question →Map Sum Pairs

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.