Design Add and Search Words Data Structure

Q: What is the time complexity of Add and Search Words?

Adding a word of length L takes O(L) , and so does a search with no dots, however many words are stored. A search with d dots takes O(26^d · L) in the worst case. Memory is O(T) nodes for T added letters.

MediumTrie Backtracking

+10

Build a word dictionary with two operations. addWord w stores the word w. search p tells whether some stored word matches the pattern p: same length, and at every position the pattern holds the same letter or a dot ., which stands for any one letter.

Operation i is ops[i] on the word or pattern words[i]. Run them in order on an empty dictionary and return one string each: "null" for an addWord, "true" or "false" for a search.

Function

wordDictionaryOps(ops: string-array, words: string-array) → string-array

opsstring-array: the operations, in the order they run
wordsstring-array: the word to add or the pattern to search for, one per operation
Returnsstring-array: one answer per operation, as text

Constraints

1 ≤ ops.length ≤ 2500
words.length == ops.length
Every ops[i] is addWord or search.
1 ≤ words[i].length ≤ 20
A word to add holds only lowercase English letters.
A pattern to search holds lowercase English letters and at most 3 dots.

Examples

Input: ops = ["addWord", "addWord", "search", "search", "search", "search"]words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
Output: ["null", "null", "true", "false", "false", "true"]
Explanation: r.se matches both words: the dot covers the o of rose and the i of rise. A dot never stands for a missing letter, so ros and rose. fail. ..s. matches, since both words have s third.

Input: ops = ["search", "addWord", "search", "search", "search"]words = ["...", "sky", "...", "s.y", "sk"]
Output: ["false", "null", "true", "true", "false"]
Explanation: The dictionary starts empty, so ... finds nothing. Once sky is added, ... and s.y both match it, while sk is too short.

Input: ops = ["addWord", "addWord", "search", "search", "search"]words = ["maple", "mango", "ma..o", "m...y", "m.p.e"]
Output: ["null", "null", "true", "false", "true"]
Explanation: The first dot of ma..o can be the p of maple or the n of mango; maple ends in e, but mango fits. No word ends in y, so m...y fails, and m.p.e matches maple.

Follow-up

How would you extend search if a pattern could also hold *, standing for any run of letters, including an empty one?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A dot means a search cannot name the word it wants: ma..o stands for 676 possible words, and only the stored ones matter. In a trie, words that start alike share one path. A letter in the pattern follows one link, a dot fans out only to children that exist, and a depth-first search backs up from dead branches.

Compare the pattern with every stored word

Intuition

Keep the added words in a list and test each one against the pattern: same length, and at every position a dot or the same letter. That is the definition of a match, checked against every stored word, so the answer is right.

Each search pays for the whole list, O(n·L) for n words of up to L letters, even a pattern with no dot. 1,250 adds followed by 1,250 searches test 1,250 × 1,250 = 1,562,500 words.

Algorithm

Keep the added words in a list. For addWord w, append w and record "null".
For search p, compare p with each word of the same length, position by position, letting a dot accept any letter.
Record "true" at the first match, or "false" if none.

def matches(pattern, word):
    # Same length, and every position holds a dot or the same letter.
    if len(pattern) != len(word):
        return False
    for p, w in zip(pattern, word):
        if p != "." and p != w:
            return False
    return True


def wordDictionaryOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "addWord":
            stored.append(word)
            result.append("null")
        else:
            found = any(matches(word, s) for s in stored)
            result.append("true" if found else "false")
    return result

Trie with a depth-first search on dots

Intuition

Put the words in a trie: rose and rise share the r node, then split into o and i. An end flag marks each node where a stored word ends. A pattern of letters is one walk down the trie. A dot may be any letter, so at a dot try every existing child and return true as soon as one leads to a match.

For ma..o, the node for ma has children p and n. Through p the second dot reaches l, which has no o child, so the search backs up and tries n: g, then o, which ends mango.

A match must use up the whole pattern on a flagged node, which settles length: ros stops on an unflagged node, and rose. runs out of links. A dot opens at most 26 branches, so d dots visit at most 26^d · L nodes, and a pattern without dots costs O(L).

Algorithm

Every node has child links and an end flag, off at first.
For addWord w: walk w down from the root, creating missing nodes, and set the end flag where the walk stops.
match(node, i): if i is the pattern's length, return the node's end flag.
If p[i] is a letter, return false if its child is missing, else match(child, i+1). If it is a dot, return true if match(child, i+1) succeeds for any existing child, else false.
Record match(root, 0) per search, "null" per add.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


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

    def add_word(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, pattern):
        return self._match(self.root, pattern, 0)

    def _match(self, node, pattern, i):
        # Can the path below node spell pattern[i:] and end on a stored word?
        if i == len(pattern):
            return node.is_end
        ch = pattern[i]
        if ch == ".":
            # A dot stands for any letter: try each child until one works.
            for child in node.children.values():
                if self._match(child, pattern, i + 1):
                    return True
            return False
        child = node.children.get(ch)
        return child is not None and self._match(child, pattern, i + 1)


def wordDictionaryOps(ops, words):
    dictionary = WordDictionary()
    result = []
    for op, word in zip(ops, words):
        if op == "addWord":
            dictionary.add_word(word)
            result.append("null")
        else:
            result.append("true" if dictionary.search(word) else "false")
    return result

Pitfalls and edge cases

Letting the first child decide a dot. In ma..o the p branch fails and the n branch succeeds, so code that returns the first child's result answers false when it tries p first. Answer false only after every child fails.
Answering true when the pattern runs out on any node. After adding rose, ros reaches a node, but no word ends there. Check the end flag.
Letting a dot match a missing letter. card. matches cards but not card.
Taking a dot as a letter. Indexing a 26-slot array with '.' - 'a' reads outside the array, so test for the dot first.

Frequently asked questions3

What is the time complexity of Add and Search Words?

Adding a word of length L takes O(L), and so does a search with no dots, however many words are stored. A search with d dots takes O(26^d · L) in the worst case. Memory is O(T) nodes for T added letters.

Can you solve it with a hash set instead of a trie?

Yes, with trade-offs. A set answers a pattern without dots in one lookup. For dots you either scan every stored word of that length, O(n·L), or fill each dot with all 26 letters and look up each result, 17,576 lookups for three dots.

Should the trie search be recursive or iterative?

Either works. The recursion goes one level per pattern letter, at most 20 here, so the call stack stays small. An iterative version keeps a stack of (node, position) pairs and pushes every child at a dot.

def wordDictionaryOps(ops, words):
    # Write code here

Test #1

Test #2

Test #3

Arguments

ops = ["addWord", "addWord", "search", "search", "search", "search"]
words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]

Expected Output

["null", "null", "true", "false", "false", "true"]