Medium

Design Add and Search Words Data Structure

LAB

Simulate addWord and search operations where . matches any single character. Return booleans for search operations.

EXAMPLES

Example 1

Input
{
  "operations": [
    "addWord",
    "addWord",
    "addWord",
    "search",
    "search",
    "search",
    "search"
  ],
  "words": [
    "bad",
    "dad",
    "mad",
    "pad",
    "bad",
    ".ad",
    "b.."
  ]
}

Output
[
  false,
  true,
  true,
  true
]

FUNCTION SHAPE

operations: stringArraywords: stringArray→boolArray

SOLUTION NOTE

Standard template, but the only tricky part is handling periods. We need to recursively call search for word[i+1:] when we see a period, on all the children of the current node, as we can match onto any of them.

Reveal reference solution +

pythonREFERENCE

def search(self, word: str) -> bool:
    node = self
    for i in range(len(word)):
        c = word[i]
        if c == '.':
            return any(child.search(word[i+1:]) for child in node.children.values())
        if c not in node.children: return False
        node = node.children[c]
    return node.is_word

TimeO(26^m) worst case where m is number of dots

SpaceO(1)

Open on LeetCode ↗