LeetCode Meditations: Design Add and Search Words Data Structure

#computerscience #algorithms #typescript #javascript

Let's start with the description for 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:

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 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.

However, searching seems to be a bit more challenging since we have to do something similar to a regex 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:

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 strings as keys, and TrieNodes 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:

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.

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:

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

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. Alternatively, we could've also used a non-null assertion operator that asserts values as non `null` or `undefined`, like this: `currentNode = currentNode.children.get(char)!;`

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.
Alternatively, we could've also used a non-null assertion operator that asserts values as non null or undefined, like this:

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.

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:

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:

return dfs(0, this.root);

Here is the final solution in TypeScript:

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 $O(n)$ where $n$ is the length of the word — because we iterate through each character once, doing a constant operation each time. The space complexity is also $O(n)$ 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— $O(n * m)$ where $n$ is the length of the word and $m$ 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 $O(h)$ where $h$ is the height of the trie, because of the recursive call stack.