Typorithm · medium

Word Dictionary (Wildcard)

word-dictionarytrieswildcarddfsbacktracking

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Word Dictionary (Wildcard)

Tries

Search with a '.' wildcard via DFS: an exact char follows one edge, while '.' branches into every child.

Adding a '.' wildcard turns trie search into a small DFS with branching.

An ordinary character follows its single edge, just like normal search.

A '.' must try every child, succeeding if any branch matches the rest of the word.

Recurse character by character.

'.' branches into all children.

Succeed at word end with isEnd.

search(word) {
  const dfs = (node, i) => {
    if (i === word.length) {
      return node.isEnd;
    }
    const ch = word[i];
    if (ch === ".") {
      for (const child of node.children.values()) {
        if (dfs(child, i + 1)) {
          return true;
        }
      }
      return false;
    }
    if (!node.children.has(ch)) {
      return false;
    }
    return dfs(node.children.get(ch), i + 1);
  };

  return dfs(this, 0);
}

Read the implementation

Connect each part of the code to the concept before you type.

1. End of word

Consuming all characters succeeds only on a word terminal.

if (i === word.length) {
      return node.isEnd;
    }

2. Wildcard branch

A dot matches any single character.

if (ch === ".") {

3. Try all children

Recurse into every child to satisfy the wildcard.

for (const child of node.children.values()) {

4. Exact match

A normal character follows its single edge.

return dfs(node.children.get(ch), i + 1)

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.