Design Add and Search Words Data Structure

mediumTrie & Strings144 stepsJava · Python · C++

Add words, and search where '.' matches any letter. Store words in a trie. Searching follows the exact child for a letter, and tries every child for a '.', using recursion.

▶ Watch the animated trace

Traced input: addWord(bad), addWord(dad), addWord(mad), search(pad), search(bad), search(.ad), search(b..) → [null, null, null, null, false, true, true, true]. Original problem: neetcode.io/problems/design-word-search-data-structure

Complexity

BestO(L)

AverageO(L)

WorstO(26^L)

SpaceO(total chars)

Searches with many dots can branch widely.

Key idea

Plain letters follow one path, exactly like a normal trie.
A '.' branches into every existing child.
Return true as soon as any branch finds a word end.

Common mistakes

Treating '.' as a literal character.
Forgetting to check isEnd at the last character.

Solution

Java

class WordDictionary {
    class Node {
        Node[] next = new Node[26];
        boolean isEnd;
    }

    private final Node root = new Node();

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

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

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

Python

class WordNode:
    def __init__(self):
        self.next = {}
        self.is_end = False


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

    def addWord(self, word: str) -> None:
        cur = self.root
        for c in word:
            cur = cur.next.setdefault(c, WordNode())
        cur.is_end = True

    def search(self, word: str) -> bool:
        return self._match(word, 0, self.root)

    def _match(self, word: str, i: int, node: WordNode) -> bool:
        if i == len(word): return node.is_end
        c = word[i]
        if c != '.':
            nxt = node.next.get(c)
            return nxt is not None and self._match(word, i + 1, nxt)
        for child in node.next.values():
            if self._match(word, i + 1, child): return True
        return False

C++

class WordDictionary {
    struct Node {
        Node* next[26] = {};
        bool isEnd = false;
    };

    Node* root = new Node();

    bool match(const string& word, size_t i, Node* node) {
        if (i == word.size()) return node->isEnd;
        char c = word[i];
        if (c != '.') {
            Node* next = node->next[c - 'a'];
            return next && match(word, i + 1, next);
        }
        for (Node* child : node->next) {
            if (!child) continue;
            if (match(word, i + 1, child)) return true;
        }
        return false;
    }

public:
    void addWord(string word) {
        Node* cur = root;
        for (char c : word) {
            if (!cur->next[c - 'a']) cur->next[c - 'a'] = new Node();
            cur = cur->next[c - 'a'];
        }
        cur->isEnd = true;
    }

    bool search(string word) {
        return match(word, 0, root);
    }
};

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
All dots Length still has to match.	`addWord(ab), search(..), search(...)`	`[null, null, true, false]`
Dot as the last letter The '.' matches 't', which is a word end.	`addWord(at), search(a.)`	`[null, null, true]`