Design Add and Search Words Data Structure

Medium Problem 96 of 151 Java and Python

Problem

Design a WordDictionary with addWord(word) and search(word). search returns true if any added word matches, where a . in the search string matches any single letter.

Example 1

Input: addWord("bad"), addWord("dad"), addWord("mad"), search("pad"), search("bad"), search(".ad"), search("b..")
Output: false, true, true, true

Constraints

1 ≤ word.length ≤ 25
Search strings have at most 2 dots.
At most 10⁴ calls.

Explanation

Store words in a trie. Searching a normal letter follows one child. A . can be any letter, so try every child at that position, recursing on the rest of the pattern.

Approach 1 · Naive

Compare against every word of the same length

Time O(N · L) per search
Space O(total characters)

Keep words grouped by length, and compare the pattern character by character with each word of that length.

addWord: append to byLength[len].
search: for each word of the same length, check every position matches or is a dot.

Java

import java.util.*;

class WordDictionary {
    private final Map<Integer, List<String>> byLength = new HashMap<>();

    public void addWord(String word) {
        byLength.computeIfAbsent(word.length(), k -> new ArrayList<>()).add(word);
    }

    public boolean search(String word) {
        for (String candidate : byLength.getOrDefault(word.length(), List.of())) {
            boolean match = true;
            for (int i = 0; i < word.length() && match; i++) {
                match = word.charAt(i) == '.' || word.charAt(i) == candidate.charAt(i);
            }
            if (match) {
                return true;
            }
        }
        return false;
    }
}

Python

from collections import defaultdict

class WordDictionary:
    def __init__(self):
        self.by_length = defaultdict(list)

    def addWord(self, word: str) -> None:
        self.by_length[len(word)].append(word)

    def search(self, word: str) -> bool:
        return any(
            all(p == "." or p == c for p, c in zip(word, candidate))
            for candidate in self.by_length[len(word)]
        )

Approach 2 · Optimal

Trie with DFS on wildcards

Time O(L) without dots; O(26^d · L) with d dots
Space O(total characters × 26)

Insert words into a trie. Search recursively: a letter follows its child; a dot tries every child.

dfs(node, i): if i == word.length, return node.end.
If word[i] is a dot, return true if any child satisfies dfs(child, i + 1).
Otherwise follow the matching child, or fail if it is missing.

Java

class WordDictionary {
    private static class Node {
        Node[] children = new Node[26];
        boolean end;
    }

    private final Node root = new Node();

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

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

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

Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end = False


class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.end = True

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return node.end
            if word[i] == ".":
                return any(dfs(child, i + 1) for child in node.children.values())
            child = node.children.get(word[i])
            return child is not None and dfs(child, i + 1)

        return dfs(self.root, 0)

Complexity compared

Approach	Time	Space
Naive Compare against every word of the same length	O(N · L) per search	O(total characters)
Optimal Trie with DFS on wildcards	O(L) without dots; O(26^d · L) with d dots	O(total characters × 26)

Key takeaways

Wildcards turn a trie walk into a DFS; the trie still prunes every branch that cannot match.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem