Design Add and Search Words Data Structure

The problem

Build a class WordDictionary with two methods:

• addWord(word) stores word.
• search(word) returns true if some stored word matches word. In word, a dot . matches any one letter. Every other letter must match exactly, and the lengths must be equal.

Each example below is a list of calls on one new WordDictionary, with what each call returns (null for addWord).

Example 1

Input: addWord("cot"), addWord("cut"), addWord("cub"), search("cat"), search("c.b"), search("cu")

Output: null, null, null, false, true, false

No word has “a” as its second letter. “c.b” matches “cub”. “cu” is only the start of “cut” and “cub”, not a whole word.

Example 2

Input: addWord("a"), search("."), search("a.")

Output: null, true, false

“.” matches the one-letter word “a”. “a.” needs two letters.

Example 3

Input: addWord("go"), search(".."), search("g")

Output: null, true, false

Two dots match any two-letter word. “g” is too short.

Constraints

• 1 ≤ word.length ≤ 25
• Words passed to addWord use only a to z. Words passed to search use a to z and ..
• A search word holds at most 2 dots.
• At most 10,000 calls in total.

Clarifying questions

Does "." match one letter or many?

Exactly one. So the lengths must be equal.

Must the match be a whole word?

Yes. "cu" does not match "cut".

How many dots can a search have?

At most 2. That keeps the branching small, as the Big O will show.

Can stored words contain dots?

No. Only search words do.

Spot the pattern

Stored words that share a start can share one path: that is a trie, the prefix tree from the previous problem. A plain letter follows one edge. A dot has to try every edge and give up on the ones that lead nowhere. Trying a choice, and going back when it fails, is backtracking.

Solutions

Brute forceO(N × L)TrieO(26ᵈ × L)

Show all

This problem has two approaches. There is no useful step between them.

Brute force O(N × L)

The idea

Keep every word in a list. To search, compare the query with each stored word. Skip words of the wrong length. Otherwise walk both words letter by letter: a dot always passes, any other letter must be equal.

It is simple and correct. But every search may compare against every stored word, and the list gives no way to skip the words that clearly cannot match.

Walkthrough

words

cot0cut1cub2

answers

nullnullnull

1. words = []
2. def addWord(word): words.append(word)
3. def search(word):
4. for stored_word in words:
5. if len(stored_word) == len(word) and all(
6. wanted_letter == "." or stored_letter == wanted_letter
7. for stored_letter, wanted_letter in zip(stored_word, word)):
8. return True
9. return False

addWord stores "cot", "cut" and "cub" in a plain list, one step each. Now answer the searches.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// Brute force: keep every word in a list and compare letter by letter,
// letting "." match anything. With N words of length L, N * L per search.
class WordDictionary {
    private final List<String> words = new ArrayList<>();

    public void addWord(String word) {
        words.add(word);
    }

    public boolean search(String word) {
        for (String storedWord : words) {
            // "." stands for exactly one letter, so the lengths must match.
            if (storedWord.length() != word.length()) continue;
            boolean ok = true;
            for (int i = 0; i < storedWord.length() && ok; i++) {
                ok = word.charAt(i) == '.' || word.charAt(i) == storedWord.charAt(i);
            }
            if (ok) return true;
        }
        return false;
    }
}

Big O

Time O(N × L)Space O(N × L)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line compares the query with one stored word. It reads letters until one fails, so one compare costs up to L steps, where L is the word length. It runs once per stored word, and there are N of them. Each letter read counts as 1 step.

   1. words = []
   2. def addWord(word): words.append(word)
   3. def search(word):
   4. for stored_word in words:
   5. if len(stored_word) == len(word) and all(
   6. wanted_letter == "." or stored_letter == wanted_letter
   7. for stored_letter, wanted_letter in zip(stored_word, word)):
   8. return True
   9. return False

2. 2 Count the runs on Example 1

   The table counts letters read on Example 1. “cat” fails at the second letter of each word: 2 + 2 + 2. “c.b” reads all 3 letters of each word before it decides. “cu” skips every word on length alone.

   6 + 9 + 0 = 15 letters read.

   search	"cat"	"c.b"	"cu"
   words compared	3	3	3
   letters read	6	9	0

   total

   6 + 9 + 0 = 15 letters read

3. 3 Write the count for any n

   In the worst case every stored word has the right length, and each compare reads all L letters:

   N × L letters per search

   Check it with “c.b”: N = 3 and L = 3, so 9 letters, as counted.

4. 4 Keep only the part that grows fastest

   There is nothing to drop: N × L has no smaller term. Each search gets slower as more words are added.

   So the time is O(N × L).

5. S Space: count the extra memory the same way

   The list keeps every word, up to N × L letters in all. The search itself keeps only a few counters. So the space is O(N × L).

   words (all letters of all words)

Trie O(26ᵈ × L)

The idea

Store the words in a trie: a tree where each edge is one letter and a flag marks where a word ends. addWord walks down from the root and adds a node for each letter that has no edge yet.

search is a recursive walk. It holds position, its place in the query, and a node in the trie.

• If position has reached the end, the match is real only if this node ends a word.
• If the letter is plain, there is one edge to follow. If it is missing, this path fails.
• If the letter is a dot, try every child. As soon as one child leads to a match, stop and return true. If a child fails, go back and try the next one.

Why it never misses the answer: each stored word is one path from the root. The search follows every path that agrees with the query, letter by letter, so if a matching word exists, its path gets tried.

Walkthrough

answers

empty

1. def addWord(word):
2. node = root
3. for letter in word:
4. node = node.children.setdefault(letter, TrieNode())
5. node.is_word = True
6. def search(word, position=0, node=root):
7. if position == len(word):
8. return node.is_word
9. letter = word[position]
10. if letter == ".":
11. return any(search(word, position + 1, child) for child in node.children.values())
12. if letter not in node.children:
13. return False
14. return search(word, position + 1, node.children[letter])

Start with an empty trie: a root, and one edge per letter below it.

← BackStep →Play1 / 16

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// Trie with a depth-first search. A letter follows one edge; a "." tries
// every child. With d dots, at most 26^d paths of length L are walked.
class WordDictionary {
    private static class Node {
        Node[] children = new Node[26];
        boolean isWord;
    }

    private final Node root = new Node();

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

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

    private boolean matchesFrom(String word, int position, Node node) {
        // All letters used: a word must end exactly here.
        if (position == word.length()) return node.isWord;
        char letter = word.charAt(position);
        // "." can be any letter, so any child may lead to a match.
        if (letter == '.') {
            for (Node child : node.children) {
                if (child != null && matchesFrom(word, position + 1, child)) return true;
            }
            return false;
        }
        // A plain letter has only one way to go.
        Node nextNode = node.children[letter - 'a'];
        return nextNode != null && matchesFrom(word, position + 1, nextNode);
    }
}

Big O

Time O(26ᵈ × L)Space O(N × L)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The work repeats through recursion, so we count the calls of search. Each call does a fixed job for one letter: a check, one lookup, or a loop over the children for a dot. So each call counts as 1 step, and a dot can start up to 26 calls. addWord takes one step per letter.

   1. def addWord(word):
   2. node = root
   3. for letter in word:
   4. node = node.children.setdefault(letter, TrieNode())
   5. node.is_word = True
   6. def search(word, position=0, node=root):
   7. if position == len(word):
   8. return node.is_word
   9. letter = word[position]
   10. if letter == ".":
   11. return any(search(word, position + 1, child) for child in node.children.values())
   12. if letter not in node.children:
   13. return False
   14. return search(word, position + 1, node.children[letter])

2. 2 Count the runs on Example 1

   The table counts calls on Example 1. “cat” makes 2 calls and stops at the missing “a”. “c.b” makes 5: the root, “c”, the dead end “o”, then “u” and “b”. “cu” makes 3.

   2 + 5 + 3 = 10 calls.

   search	"cat"	"c.b"	"cu"
   calls	2	5	3
   dots	0	1	0

   total

   2 + 5 + 3 = 10 calls

3. 3 Write the count for any n

   A query without dots follows one path, so at most L + 1 calls. Each dot can multiply the number of paths by up to 26, one per letter. With d dots:

   at most 26ᵈ × (L + 1) calls

   Check it with “c.b”: d = 1 and L = 3, so the bound is 26 × 4 = 104. The real trie had only 2 children under “c”, so the search made 5 calls.

4. 4 Keep only the part that grows fastest

   Drop the + 1. One extra call per path does not change the growth. What is left is 26ᵈ × L. The constraints say d ≤ 2, so the factor 26ᵈ is at most 676, a fixed number. For queries without dots, the search is O(L), however many words are stored. addWord is always O(L).

   So the time is O(26ᵈ × L).

5. S Space: count the extra memory the same way

   The trie holds at most one node per letter added, so N × L nodes in the worst case, and fewer when words share starts. The search adds a call stack L + 1 deep. So the space is O(N × L).

   trie nodes (one per new letter)call stack (L frames)

Common mistake

Returning the first child's answer for a dot

Writing return search(first child) for a dot gives up after one guess. In Example 1, “c.b” would try “o”, fail and return false. A dot must try every child and return true if any of them matches.

Tested at the limits

2,000 random call sequences of 1 to 15 calls, on words of 1 to 4 letters made of a, b and c, with up to two dots anywhere in a search. The brute force and the trie gave the same answers every time.

Largest inputs	Result
10,000 calls (the most allowed): 5,000 words of 25 letters that start with all 676 two-letter pairs, then 5,000 searches that start with two dots. Trie.	3.4 s, and about 4.5 MB of extra memory. Each search follows all 676 paths to the end, which is the 26ᵈ part of the time with d = 2.