Design Add And Search Words Data Structure

The problem

Build a word dictionary that can match patterns. You get a list operations of operation names and a list values with the arguments of each operation, in the same order. Carry the operations out in order and return a list with one result for each. "WordDictionary" comes first and creates an empty dictionary. "addWord" stores its word. "search" gives true if some stored word matches its pattern, which is made of lowercase letters and dots, and false otherwise. A dot matches any single letter, and a pattern matches only words of its own length. "WordDictionary" and "addWord" give null.

What to write

function solve(operations: string[], values: string[][]): (boolean | null)[]

Input
operations = ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
values = [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]

Output
[null,null,null,null,false,true,true,true]

Input
operations = ["WordDictionary","addWord","search","search"]
values = [[],["a"],["."],[".."]]

Output
[null,null,true,false]

Constraints

Return null for construction and additions; words contain lowercase letters.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Words use only the 26 lowercase letters, so a dot has at most 26 possible meanings. A pattern without dots names exactly one word, and finding that one word should not mean reading all the others.

2. Hint 2: Ask a smaller question

   Say bad, dad and mad are stored and you search for ".ad". The first position could be b, d or m. Once you choose one of them, what part of the pattern is left, and which stored words could still match?

3. Hint 3: Name the pattern

   Checking words letter by letter against a pattern is the signal for a trie: a tree where each step down is one letter and a mark shows where a word ends. A letter takes only the step down for that letter. A dot must try every step down, because any of them might lead to a match. Read the lesson on trie.

4. Hint 4: State the invariant

   A search starts at a node, one stop on a path, with a position in the pattern. It asks: does the rest of the pattern match the rest of some stored word from here? If the pattern is used up, the answer is whether the node is marked. Otherwise it comes from the steps down that the next character allows.

5. Hint 5: Sketch the pseudocode

   add: walk the letters, creating missing nodes, and mark the last. search(node, i): if i equals the pattern's length, return node's mark. For a dot, return true if search(child, i + 1) is true for any child, else false. For a letter, return false if the child is missing, else search(that child, i + 1). Call search(root, 0).

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Store words in a trie. Ordinary characters follow one edge; a dot branches over every child at that depth.

The slow way

Keep the added words in a list. To search, compare the pattern with each stored word of the same length, letter by letter, where a dot matches anything. It is correct, but a search may have to look at every stored word, and words that begin the same are compared again and again.

The insight

Store the words in a trie: a tree with one step per letter, where words that begin the same share their first steps. A letter of the pattern then has at most one way to continue. A dot is the only place with several, and after choosing one, what is left is the same question about a shorter pattern.

Step by step

1. Start with an empty root node: no children, not the end of a word. A node is one stop on a path of letters. It keeps a child for each letter that can come next, and a mark for the end of a word. The root is the stop before any letter.
2. To add a word, follow its letters, adding each node that is missing. Each letter is one step down. A node that already exists is reused, so words with the same beginning share their first steps.
3. Mark the last node as the end of a word. A path can be the beginning of a longer word. Only the mark says that a word ends here, and the search needs it to tell a whole match from a partial one.
4. When the pattern is used up, the node must be the end of a word. Every position of the pattern has matched a step down. If the node is not marked, the stored words below it are longer than the pattern, and a pattern matches only words of its own length.
5. A dot can be any letter: try every child, and one match is enough. The dot matches one letter, and you cannot tell in advance which child leads to a match, so each child is a possibility. One child that matches gives true; if none does, the answer is false.
6. A letter must follow its own child; with no such child, no match. Only the child for that letter can continue a matching word. If there is none, no stored word begins this way, so the answer is false without looking further.
7. Carry out the operations in order and collect one result for each. The operations arrive as one list, so the answer is a list too: null for WordDictionary and addWord, true or false for each search.

The same numbered steps are the comments in each solution.

function solve(operations, values) {
  // 1. Start with an empty root node: no children, not the end of a word
  const root = { end: false, children: new Map() };

  // 2. To add a word, follow its letters, adding each node that is missing
  function add(word) {
    let node = root;
    for (const letter of word) {
      if (!node.children.has(letter)) {
        node.children.set(letter, { end: false, children: new Map() });
      }
      node = node.children.get(letter);
    }
    // 3. Mark the last node as the end of a word
    node.end = true;
  }

  // 4. When the pattern is used up, the node must be the end of a word
  function search(node, pattern, i) {
    if (i === pattern.length) return node.end;
    // 5. A dot can be any letter: try every child, and one match is enough
    if (pattern[i] === ".") {
      for (const child of node.children.values()) {
        if (search(child, pattern, i + 1)) return true;
      }
      return false;
    }
    // 6. A letter must follow its own child; with no such child, no match
    if (!node.children.has(pattern[i])) return false;
    return search(node.children.get(pattern[i]), pattern, i + 1);
  }

  // 7. Carry out the operations in order and collect one result for each
  const out = [];
  for (let i = 0; i < operations.length; i++) {
    const op = operations[i];
    const args = values[i];
    let result = null;
    if (op === "addWord") {
      add(args[0]);
    } else if (op === "search") {
      result = search(root, args[0], 0);
    }
    out.push(result);
  }
  return out;
}

function solve(operations: string[], values: string[][]): (boolean | null)[] {
  // A node keeps its children by letter and whether a word ends at it.
  type Node = { end: boolean; children: Map<string, Node> };

  // 1. Start with an empty root node: no children, not the end of a word
  const root: Node = { end: false, children: new Map() };

  // 2. To add a word, follow its letters, adding each node that is missing
  function add(word: string): void {
    let node = root;
    for (const letter of word) {
      if (!node.children.has(letter)) {
        node.children.set(letter, { end: false, children: new Map() });
      }
      node = node.children.get(letter)!;
    }
    // 3. Mark the last node as the end of a word
    node.end = true;
  }

  // 4. When the pattern is used up, the node must be the end of a word
  function search(node: Node, pattern: string, i: number): boolean {
    if (i === pattern.length) return node.end;
    // 5. A dot can be any letter: try every child, and one match is enough
    if (pattern[i] === ".") {
      for (const child of node.children.values()) {
        if (search(child, pattern, i + 1)) return true;
      }
      return false;
    }
    // 6. A letter must follow its own child; with no such child, no match
    if (!node.children.has(pattern[i])) return false;
    return search(node.children.get(pattern[i])!, pattern, i + 1);
  }

  // 7. Carry out the operations in order and collect one result for each
  const out: (boolean | null)[] = [];
  for (let i = 0; i < operations.length; i++) {
    const op = operations[i];
    const args = values[i];
    let result: boolean | null = null;
    if (op === "addWord") {
      add(args[0]);
    } else if (op === "search") {
      result = search(root, args[0], 0);
    }
    out.push(result);
  }
  return out;
}

def solve(operations, values):
    # 1. Start with an empty root node: no children, not the end of a word
    root = {"end": False, "children": {}}

    # 2. To add a word, follow its letters, adding each node that is missing
    def add(word):
        node = root
        for letter in word:
            if letter not in node["children"]:
                node["children"][letter] = {"end": False, "children": {}}
            node = node["children"][letter]
        # 3. Mark the last node as the end of a word
        node["end"] = True

    # 4. When the pattern is used up, the node must be the end of a word
    def search(node, pattern, i):
        if i == len(pattern):
            return node["end"]
        # 5. A dot can be any letter: try every child, and one match is enough
        if pattern[i] == ".":
            for child in node["children"].values():
                if search(child, pattern, i + 1):
                    return True
            return False
        # 6. A letter must follow its own child; with no such child, no match
        if pattern[i] not in node["children"]:
            return False
        return search(node["children"][pattern[i]], pattern, i + 1)

    # 7. Carry out the operations in order and collect one result for each
    out = []
    for op, args in zip(operations, values):
        result = None
        if op == "addWord":
            add(args[0])
        elif op == "search":
            result = search(root, args[0], 0)
        out.append(result)
    return out

Example 1, traced

Input
operations = ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
values = [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]

Output
[null,null,null,null,false,true,true,true]

Why it works

A search from a node answers whether the rest of the pattern matches the rest of some stored word from there. A letter allows one child and a dot allows every child, and the answer is true if any allowed child gives true. When the pattern is used up, the answer is whether the node is marked.

Time and space

Time O(26^L) worst-case search; O(L) add, extra space O(total inserted characters). Adding follows one node per letter: O(L) for a word of L letters. A search does the same until a dot, which tries each of at most 26 children. A pattern of L dots can branch at every level: O(26^L) in the worst case. Space is O(total inserted characters).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• When the pattern is used up, check the mark. If you return true instead, ba matches bad, because the path for ba exists, and the pattern ".." matches bad too.
• One matching child is enough. Trying only the first child, or needing every child to match, makes ".ad" answer false when bed was added before dad, although dad matches.
• Answer false when a letter has no child. If the search steps into the missing child anyway, search pad in example 1 fails with an error instead of answering false.

Pattern

Trie. Builds on Maximum Depth of Binary Tree and Implement Trie Prefix Tree.

Keep going