Design Add and Search Words Data Structure

Medium Tries Basics Original on LeetCode

Design Add and Search Words Data Structure is a medium tries problem solved with the basics pattern. The best approach, optimal (trie with dfs on dots), runs in add O(L), search O(26^d · L) time and O(total characters · 26) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (list of words) up.

Problem

Design a WordDictionary class that stores words and answers lookup queries in which some letters may be unknown.

  • WordDictionary() creates an empty dictionary.
  • addWord(word) stores word.
  • search(word) returns true if some stored word matches word exactly, where every . in word may stand for any single letter. Otherwise it returns false.

A query matches only a whole stored word of the same length; matching a prefix is not enough.

Examples

Example 1

Input
addWord("lamp"), addWord("limp"), addWord("lam"), search("l.mp"), search("lam"), search("la"), search("..m")
Output
true, true, false, true
Why
"l.mp" fits both "lamp" and "limp"; "la" is only a prefix, not a stored word; "..m" matches "lam".

Example 2

Input
addWord("go"), search("."), search("g."), search("..o")
Output
false, true, false
Why
A dot stands for exactly one letter, so the length must match too.

Constraints

  • 1 <= word.length <= 25
  • Words passed to addWord contain only lowercase English letters.
  • Words passed to search contain lowercase letters and .; at most 2 dots per query.
  • At most 10^4 calls in total to addWord and search.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (list of words)add O(1), search O(N · L)O(N · L)
Optimal (trie with DFS on dots)add O(L), search O(26^d · L)O(total characters · 26)

1Brute force (list of words)

Timeadd O(1), search O(N · L)A search may compare against all N stored words, L characters each.
SpaceO(N · L)Every stored character is kept.

Keep every added word in a list. For a search, compare the query with each stored word of the same length, letting . match anything.

  1. addWord appends to the list.
  2. search loops over the list; skip words of another length; compare character by character, treating '.' as a match.
class WordDictionary {
    private final List<String> words = new ArrayList<>();

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

    public boolean search(String word) {
        for (String w : words) {
            if (w.length() != word.length()) continue;
            boolean ok = true;
            for (int i = 0; i < w.length() && ok; i++)
                if (word.charAt(i) != '.' && word.charAt(i) != w.charAt(i)) ok = false;
            if (ok) return true;
        }
        return false;
    }
}

2Optimal (trie with DFS on dots)

Timeadd O(L), search O(26^d · L)Each of the at most d = 2 dots can branch 26 ways; letters follow a single path.
SpaceO(total characters · 26)One trie node per distinct prefix, each with 26 child slots.

Insert each word into a trie and mark the node where it ends. A search walks the trie: a letter moves to that one child, while a dot branches into every existing child. Shared prefixes are stored once, and a search only visits paths that exist.

  1. Node: children[26] and an end flag.
  2. addWord: walk/create children for each letter, set end = true at the last node.
  3. search(i, node): if i == length return node.end; if word[i] is '.', return true if any child succeeds; else follow that child if it exists.
class WordDictionary {
    private static class Node {
        Node[] next = new Node[26];
        boolean end;
    }

    private final Node root = new Node();

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

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

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

Edge cases to test

  • Searching before anything is added
  • A query that is a prefix of a stored word (must be false)
  • A query made only of dots
  • Adding the same word twice

Hints

Hint 1

Store the words in a trie so that every prefix is shared.

Hint 2

A letter follows one child; a dot has to try every child of the current node.

FAQ

What is the best time complexity for Design Add and Search Words Data Structure?

Optimal (trie with DFS on dots) runs in add O(L), search O(26^d · L) time and O(total characters · 26) extra space. Each of the at most d = 2 dots can branch 26 ways; letters follow a single path.

Which pattern does Design Add and Search Words Data Structure use?

It is a tries problem that uses the basics pattern. Other problems with the same pattern: Implement Trie (Prefix Tree), Implement Trie ll, Design In-Memory File System.

Is there a brute force solution for Design Add and Search Words Data Structure?

Yes. Brute force (list of words) takes add O(1), search O(N · L) time and O(N · L) space. Keep every added word in a list.

Which edge cases should I test for Design Add and Search Words Data Structure?

Searching before anything is added; A query that is a prefix of a stored word (must be false); A query made only of dots; Adding the same word twice.