Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Wildcard Trie
DSA

Wildcard Trie

Understand how trie traversal can be extended to support wildcard characters and flexible matching.

A normal trie walk follows exactly one child per character. A . wildcard breaks that — try ALL children at that depth.

Focus on recognizing:

“Search with . matching any letter” → trie + branching DFS

Pattern 1: WordDictionary (Add + Wildcard Search)

Searching ".ad" in a dictionary of bad/dad/mad — the first dot branches into all three roots. Press ▶ to animate.

Wildcard Search (Multiple Dots)

Match patterns like '.ad' and 'b..' against words stored in a trie, where '.' matches any character.

Each '.' fans the recursion into all children; literal characters follow the single matching child. The isEnd flag is what separates a prefix from a full word.

TRIE VISUALIZER
Steps –
bdmaaad★d★d★
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        search(node, i):
                      
                        2
                          if i == len(word): return node.isEnd
                      
                        3
                          ch = word[i]
                      
                        4
                          if ch == '.': try ALL children (branch)
                      
                        5
                          else: follow the one matching child
                      
class WordDictionary {
    private final WordDictionary[] children = new WordDictionary[26];
    private boolean isEnd;

    public void addWord(String word) {
        WordDictionary cur = this;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null)
                cur.children[i] = new WordDictionary();
            cur = cur.children[i];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        return dfs(this, word, 0);
    }

    private boolean dfs(WordDictionary node, String word, int i) {
        if (i == word.length()) return node.isEnd;

        char c = word.charAt(i);

        if (c == '.') {                       // branch everywhere
            for (WordDictionary child : node.children)
                if (child != null
                        && dfs(child, word, i + 1))
                    return true;
            return false;
        }

        WordDictionary next = node.children[c - 'a'];
        return next != null && dfs(next, word, i + 1);
    }
}
class WordDictionary:
    def __init__(self):
        self.children = {}
        self.is_end = False

    def add_word(self, word):
        cur = self
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = WordDictionary()
            cur = cur.children[ch]
        cur.is_end = True

    def search(self, word):
        return self._dfs(word, 0)

    def _dfs(self, word, i):
        if i == len(word):
            return self.is_end

        ch = word[i]

        if ch == ".":                 # branch everywhere
            return any(child._dfs(word, i + 1)
                       for child in self.children.values())

        child = self.children.get(ch)
        return child is not None and child._dfs(word, i + 1)
struct Node {
    Node* children[26] = {};
    bool isEnd = false;
};

class WordDictionary {
    Node root;

    bool dfs(Node* node, const string& w, int i) {
        if (i == (int)w.size()) return node->isEnd;

        char c = w[i];

        if (c == '.') {               // branch everywhere
            for (Node* child : node->children)
                if (child && dfs(child, w, i + 1))
                    return true;
            return false;
        }

        Node* next = node->children[c - 'a'];
        return next && dfs(next, w, i + 1);
    }

public:
    void addWord(const string& word) {
        Node* cur = &root;
        for (char c : word) {
            auto& next = cur->children[c - 'a'];
            if (!next) next = new Node();
            cur = next;
        }
        cur->isEnd = true;
    }

    bool search(const string& word) {
        return dfs(&root, word, 0);
    }
};
class WordDictionary {
  root = { children: {}, isEnd: false };

  addWord(word) {
    let cur = this.root;
    for (const ch of word) {
      if (!cur.children[ch]) cur.children[ch] = { children: {}, isEnd: false };
      cur = cur.children[ch];
    }
    cur.isEnd = true;
  }

  search(word) {
    const dfs = (node, i) => {
      if (i === word.length) return node.isEnd;

      const ch = word[i];

      if (ch === ".") {
        // branch everywhere
        for (const child of Object.values(node.children))
          if (dfs(child, i + 1)) return true;
        return false;
      }

      const next = node.children[ch];
      return next !== undefined && dfs(next, i + 1);
    };

    return dfs(this.root, 0);
  }
}

Literal characters follow one path; only . fans out. Worst case explodes when the pattern is mostly dots.

. multiplies paths; letters prune them. The isEnd check at full length closes each branch.

Pattern 2: Count Matches Instead of Short-Circuiting

’.’ fans out to all children; count every surviving end.

Wildcard Search ('.')

Search a pattern where '.' matches any single character, against words stored in a trie.

Walk the pattern; at a '.' branch into every child, otherwise follow the exact character. A match is a path that consumes the whole pattern and ends on a word-end node.

TRIE VISUALIZER
Steps –
Rbad★t★
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        search(node, i):
                      
                        2
                          word[i] == '.' → try ALL children
                      
                        3
                          else → follow exact child
                      
                        4
                        match when i == len and node.isEnd

Return a count — collect every match, don’t stop at the first:

public int countMatches(String pattern) {
    return count(root, pattern, 0);
}

private int count(Node node, String p, int i) {
    if (i == p.length()) return node.isEnd ? 1 : 0;

    char c = p.charAt(i);

    if (c == '.') {
        int sum = 0;
        for (Node child : node.children)
            if (child != null)
                sum += count(child, p, i + 1);
        return sum;
    }

    Node next = node.children[c - 'a'];
    return next == null ? 0 : count(next, p, i + 1);
}
def count_matches(node, pattern, i=0):
    if i == len(pattern):
        return 1 if node.is_end else 0

    ch = pattern[i]

    if ch == ".":
        return sum(count_matches(child, pattern, i + 1)
                   for child in node.children.values())

    child = node.children.get(ch)
    return 0 if child is None \
        else count_matches(child, pattern, i + 1)
int countMatches(const string& pattern) {
    return count(&root, pattern, 0);
}

private:
int count(Node* node, const string& p, int i) {
    if (i == (int)p.size())
        return node->isEnd ? 1 : 0;

    char c = p[i];

    if (c == '.') {
        int sum = 0;
        for (Node* child : node->children)
            if (child)
                sum += count(child, p, i + 1);
        return sum;
    }

    Node* next = node->children[c - 'a'];
    return next ? count(next, p, i + 1) : 0;
}
function countMatches(node, pattern, i = 0) {
  if (i === pattern.length) return node.isEnd ? 1 : 0;

  const ch = pattern[i];

  if (ch === ".")
    return [...Object.values(node.children)].reduce(
      (sum, child) => sum + countMatches(child, pattern, i + 1),
      0,
    );

  const next = node.children[ch];
  return next ? countMatches(next, pattern, i + 1) : 0;
}

Sum over branches instead of boolean OR — same traversal, different fold.

Common Mistakes

Short-circuiting inside a counting variant.

any()/early-return answers “does it exist” — counting must visit every surviving branch.

Forgetting the isEnd check.

".a" would wrongly match "bad"’s prefix path and report success mid-word.

Treating . as matching zero or many characters.

It matches EXACTLY ONE character — no skipping depths.

Complexity

PatternTimeSpace
No wildcardsO(m)O(1)
k wildcardsO(26^k · m) worstO(m) recursion
Typical dictionaryfar less — dead branches die instantly

My Private Notes

Notes are auto-saved locally to this device.