Design Add and Search Words — Trie with Wildcard DFS

Problem

addWord(word) adds a word. search(word) searches with . as wildcard matching any single char.

Approach

Standard trie insert. For search: DFS on trie nodes. When . encountered, recurse into all non-null children.

Time: O(L) insert, O(26^L) worst search (all dots) | Space: O(total chars)

Solutions

Python

class WordDictionary:
    def __init__(self):
        self.root={}
    def addWord(self, word: str) -> None:
        node=self.root
        for c in word:
            if c not in node: node[c]={}
            node=node[c]
        node['#']=True
    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i==len(word): return '#' in node
            c=word[i]
            if c=='.':
                return any(dfs(node[k],i+1) for k in node if k!='#')
            if c not in node: return False
            return dfs(node[c],i+1)
        return dfs(self.root,0)

C++

class WordDictionary {
    struct Node{unordered_map<char,Node*>ch;bool end=false;};
    Node* root=new Node();
    bool dfs(Node* n,const string& w,int i){
        if(i==w.size()) return n->end;
        if(w[i]=='.'){for(auto&[c,nx]:n->ch)if(dfs(nx,w,i+1))return true;return false;}
        return n->ch.count(w[i])&&dfs(n->ch[w[i]],w,i+1);
    }
public:
    void addWord(string w){Node* c=root;for(char x:w){if(!c->ch[x])c->ch[x]=new Node();c=c->ch[x];}c->end=true;}
    bool search(string w){return dfs(root,w,0);}
};

Complexity

Insert: O(L) | Search: O(26^L) worst case for all-dot pattern