LeetCode Meditations: Design Add and Search Words Data Structure
Tags: computerscience, algorithms, typescript, javascript
Published: 2024-05-28 20:35:36

Let's start with the description for [Design Add and Search Words Data Structure](https://leetcode.com/problems/design-add-and-search-words-data-structure):

> Design a data structure that supports adding new words and finding if a string matches any previously added string.
>
> Implement the `WordDictionary` class:
> - `WordDictionary()` Initializes the object.
> - `void addWord(word)` Adds `word` to the data structure, it can be matched later.
> - `bool search(word)` Returns `true` if there is any string in the data structure that matches `word` or `false` otherwise. `word` may contain dots `'.'` where dots can be matched with any letter.

For example:

```ts
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord('bad');
wordDictionary.addWord('dad');
wordDictionary.addWord('mad');
wordDictionary.search('pad'); // return False
wordDictionary.search('bad'); // return True
wordDictionary.search('.ad'); // return True
wordDictionary.search('b..'); // return True
```

We also have some constraints:

- `1 <= word.length <= 25`
- `word` in `addWord` consists of lowercase English letters.
- `word` in `search` consists of `'.'` or lowercase English letters.
- There will be at most `2` dots in `word` for `search` queries.
- At most `10^4` calls will be made to `addWord` and `search`.

---

Since we're dealing with words, especially _storing_ and _searching_ a lot of words, [the trie data structure](https://rivea0.github.io/blog/leetcode-meditations-chapter-10-tries) can be efficient to use here.

Adding words is easy — in fact, we've seen how to insert a word into a trie in [the previous problem](https://rivea0.github.io/blog/leetcode-meditations-implement-trie-prefix-tree).

However, searching seems to be a bit more challenging since we have to do something similar to a [regex](https://en.wikipedia.org/wiki/Regular_expression) search, using the dot character as a wildcard.

Before that, let's take a deep breath, and start with creating a simple trie node.

---

A simple trie node might look like this:

```ts
class TrieNode {
  public children: Map<string, TrieNode>;
  public isEndOfWord: boolean;

  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}
```

Our `TrieNode` class has `children` that is a `Map` with `string`s as keys, and `TrieNode`s as values.

It also has an `isEndOfWord` flag to mark the node as the end character of a word.

The `WordDictionary` class is going to be a trie, so we can initialize our root node in the `constructor`:

```ts
class WordDictionary {
  public root: TrieNode;

  constructor() {
    this.root = new TrieNode();    
  }
  ...
}
```

Adding a word is the exact same thing we did in `insert` function of [the previous problem](https://rivea0.github.io/blog/leetcode-meditations-implement-trie-prefix-tree).

We'll traverse each character, and one by one, add it to our trie. We'll create a `currentNode` that initially points to the root node, and update it as we go. At the end, we'll mark the last node as the end of the word:

```ts
addWord(word: string): void {
  let currentNode = this.root;

  for (const char of word) {
    if (!currentNode.children.has(char)) {
      currentNode.children.set(char, new TrieNode());
    }

    currentNode = currentNode.children.get(char) as TrieNode;
  }

  currentNode.isEndOfWord = true;
}
```

| Note |
| :-- |
| Similar to the previous problem, we're casting `currentNode.children.get(char)` as a `TrieNode`, because TypeScript thinks that it might be `undefined`. This is one of those times that we know more than the TS compiler, so we're using a [type assertion](https://www.typescriptlang.org/docs/handbook/2/everyday-types.html#type-assertions). <br> Alternatively, we could've also used a [non-null assertion operator](https://www.typescriptlang.org/docs/handbook/2/everyday-types.html#non-null-assertion-operator-postfix) that asserts values as non `null` or `undefined`, like this: <br> <br> `currentNode = currentNode.children.get(char)!;` |

Now, it gets a little confusing when we need to implement `search`. We need to be able to match any letter for a dot, and the idea here is about _recursively checking the nodes_. 

For example, if we are to search for `a.c`, first we check if `a` exists, then go on to its children two levels below to see if `c` exists as the last character. If we don't reach our goal on our first try, we need to _backtrack_, and search through the other children of `a` again.

So, the idea is that if the current character of the `word` we're searching for is a dot (`.`), then, we'll go through the children of the current node, and _do the same thing for each child, continuing with each character in the `word`_.

Let's see another example.

If the word is `s.y`, we first check if `s` exists as a child node of the root, if so, we go on to check if it has any child node that has a child node of `y`, and it marks the end of the word. We could have `say` or `sky` or `spy`, etc., it doesn't matter. As soon as it matches our criteria, we can return `true` immediately.

Note that for each child, we're essentially doing the same thing, but with the next character in `word` — it's a recursive function. In fact, it's a [depth-first search](https://rivea0.github.io/blog/leetcode-meditations-chapter-7-trees#dfs).

We'll keep track of the current index of the character we're looking at in `word` as well as the current node.

If the character is a dot (`.`), we'll go on to check each child, incrementing the current character index. Otherwise, we'll do our usual search. If the character is not in the children of the current node, we can return `false` immediately. If we have that character, we'll recursively search again, incrementing the character index and updating the current node:

```ts
function dfs(currentCharIdx: number, currentNode: TrieNode) {
  if (currentCharIdx === word.length) {
    return currentNode.isEndOfWord;
  }

  const char = word[currentCharIdx];

  if (char === '.') {
    for (const child of currentNode.children.values()) {
      if (dfs(currentCharIdx + 1, child)) {
        return true;
      }
    }
    return false;
  } else {
    if (!currentNode.children.has(char)) {
      return false;
    }
    
    return dfs(currentCharIdx + 1, currentNode.children.get(char) as TrieNode);
  }
}
```

And, inside `search`, we can simply return whatever this function returns, passing it the first index of `word` and our `root` as arguments:

```ts
return dfs(0, this.root);
```

Here is the final solution in TypeScript:

```ts
class TrieNode {
  public children: Map<string, TrieNode>;
  public isEndOfWord: boolean;

  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

class WordDictionary {
  public root: TrieNode;

  constructor() {
    this.root = new TrieNode();
  }

  addWord(word: string): void {
    let currentNode = this.root;

    for (const char of word) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(char, new TrieNode());
      }
      currentNode = currentNode.children.get(char) as TrieNode;
    }
    currentNode.isEndOfWord = true;
  }

  search(word: string): boolean {
    function dfs(currentCharIdx: number, currentNode: TrieNode) {
      if (currentCharIdx === word.length) {
        return currentNode.isEndOfWord;
      }

      const char = word[currentCharIdx];

      if (char === '.') {
        for (const child of currentNode.children.values()) {
          if (dfs(currentCharIdx + 1, child)) {
            return true;
          }
        }
        return false;
      } else {
        if (!currentNode.children.has(char)) {
          return false;
        }
        
        return dfs(currentCharIdx + 1, currentNode.children.get(char) as TrieNode);
      }
    }
    
    return dfs(0, this.root);
  }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * var obj = new WordDictionary()
 * obj.addWord(word)
 * var param_2 = obj.search(word)
 */
```

#### Time and space complexity

The time complexity of adding a word is {% katex inline %} O(n) {% endkatex %} where {% katex inline %} n {% endkatex %} is the length of the word — because we iterate through each character once, doing a constant operation each time. The space complexity is also {% katex inline %} O(n) {% endkatex %} as our need for additional space will grow as the length of the word we're adding grows.

The time complexity of searching is—I think—{% katex inline %} O(n * m) {% endkatex %} where {% katex inline %} n {% endkatex %} is the length of the word and {% katex inline %} m {% endkatex %} is the total number of nodes. In the worst case where all the characters are dots, we'll search the entire tree for the word. The space complexity will be {% katex inline %} O(h) {% endkatex %} where {% katex inline %} h {% endkatex %} is the height of the trie, because of the recursive call stack.

---

Next up, we'll look at the last problem in this chapter, [Word Search II](https://leetcode.com/problems/word-search-ii). Until then, happy coding.