Command Palette

Search for a command to run...

Hectal
Problem 19.2 · TrieMedium

Design Add and Search Words

PatternTrie (Prefix Tree)Backtracking

What it teaches: Wildcard search: DFS over every child at a ..

Practise it on judges as “Design Add and Search Words Data Structure”.

The problem

Design WordDictionary with addWord(word) and search(word), where . in the search matches any one letter.

Example 1

Input: add bad, dad, mad; search pad, bad, .ad, b..
Output: false, true, true, true

Constraints

  • Search words contain at most 2 dots
  • Lowercase letters

Pattern clues in the wording

  • → Wildcard matching against a dictionary

These clues point to Trie (Prefix Tree): Store words character by character in a tree so every prefix is a path you can walk in O(length).

Stuck? Take one hint at a time

WordDictionary.java · starter
class WordDictionary {
    public WordDictionary() {}
    public void addWord(String word) {}
    public boolean search(String word) { return false; }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
ops = ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
args = [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
[null,null,null,null,false,true,true,true]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Trie with recursive search · O(L) add; O(26^dots × L) search worst case
1

Trie with recursive search

Time O(L) add; O(26^dots × L) search worst case Space O(total characters)

At index i: if i == length return node.isWord. If word[i] is a dot, return true if any child matches the rest; else follow that letter's child.

Approach 1
class WordDictionary {
    private static class Node {
        Node[] next = new Node[26];
        boolean isWord;
    }

    private final Node root = new Node();

    public WordDictionary() {}

    public void addWord(String word) {
        Node n = root;
        for (char c : word.toCharArray()) {
            if (n.next[c - 'a'] == null) n.next[c - 'a'] = new Node();
            n = n.next[c - 'a'];
        }
        n.isWord = true;
    }

    public boolean search(String word) {
        return match(root, word, 0);
    }

    private boolean match(Node n, String w, int i) {
        if (i == w.length()) return n.isWord;
        char c = w.charAt(i);
        if (c == '.') {
            for (Node child : n.next) if (child != null && match(child, w, i + 1)) return true;
            return false;
        }
        Node child = n.next[c - 'a'];
        return child != null && match(child, w, i + 1);
    }
}

Verdict: Dots are rare in practice.

Before you submit

Edge cases and common mistakes

Test these inputs

  • All dots
  • Dot at the end

Mistakes people make

  • Treating the dot as a literal character.

Interview

Follow-up questions

How could you speed up all-dot searches?