LeetCode Meditations: Word Search II
Tags: computerscience, algorithms, typescript, javascript
Published: 2024-06-01 19:05:53

Let's start with the description for [Word Search II](https://leetcode.com/problems/word-search-ii):

> Given an `m x n` `board` of characters and a list of strings `words`, return _all words on the board_.
>
> Each word must be constructed from letters of sequentially adjacent cells, where **adjacent cells** are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example:

<img src="https://assets.leetcode.com/uploads/2020/11/07/search1.jpg" alt="Example image 1" />

```
Input: board = [
  ['o', 'a', 'a', 'n'],
  ['e', 't', 'a', 'e'],
  ['i', 'h', 'k', 'r'],
  ['i', 'f', 'l', 'v'],
], words = ['oath', 'pea', 'eat', 'rain']

Output: ['eat', 'oath']
```

Or:

<img src="https://assets.leetcode.com/uploads/2020/11/07/search2.jpg" alt="Example image 2" />

```
Input: board = [
  ['a', 'b'], 
  ['c', 'd']
], words = ['abcb']

Output: []
```

Also, our constraints are:

- `m == board.length`
- `n == board[i].length`
- `1 <= m, n <= 12`
- `board[i][j]` is a lowercase English letter.
- `1 <= words.length <= 3 * 10^4`
- `1 <= words[i].length <= 10`
- `words[i]` consists of lowercase English letters.
- All the strings of `words` are unique.

---

We've seen the first iteration of this problem where we needed to search for only one word.
It's easy to think that, well, we can just loop over the words this time, and return those that our board has. Simple as that.

For example, if you remember the `exist` function (which uses depth-first search) that [we implemented in the previous version of this problem](https://rivea0.github.io/blog/leetcode-meditations-word-search), you might think that it's easy to do this:

```ts
function findWords(board: string[][], words: string[]): string[] {
  let result = [];

  for (const word of words) {
    if (exist(board, word)) {
      result.push(word);
    }
  }

  return result;
}
```

However, this is going to be a terrible approach with a runtime of probably {% katex inline %} O(\text{length of rows } * \text{length of columns } * 4^{\text{length of the word }} * \text{ number of words}) {% endkatex %}.

| Note |
| :-- |
| In `exist`, we [used](https://rivea0.github.io/blog/leetcode-meditations-word-search) depth-first search to look for the up, down, left and right directions — hence, {% katex inline %} 4^\text{length of the word} {% endkatex %}. |

If we try that, we'll treat ourselves a good old **Time Limit Exceeded** error in one of the test cases. So, we need to find another way to solve this problem — which means it's time to take a deep breath.

---

Instead of going through each word in `words` and looking for it in `board`, we can look through `board` first. If the character we're looking at is in `words`, then we'll continue searching through its directions until we find the complete word (or not). 

Because we're doing a character lookup (or basically, a _prefix search_), [trie](https://rivea0.github.io/blog/leetcode-meditations-chapter-10-tries) is going to be an efficient choice of data structure here.

Let's start with creating our simple trie node which has `children`, and a flag `isEndOfWord` to mark it as the end of the word character:

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

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

Then, we'll create our trie, but for now, we'll only have an `addWord` method. This is exactly what we've seen for the last two problems, so it's easy:

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

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

  addWord(word: string) {
    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;
  }
}
```

Traversing each character in `word`, we add it to our trie, updating the current node (which starts as our root node, of course) as we go. Once we reach the last character, we mark it as the end of the word.

| Note |
| :-- |
| Similar to the previous problems, 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, the first thing to do if we want to look up the words in our trie is... to add them to our trie, of course!
Inside the `findWords` function, we can do that easily:

```ts
let trie = new Trie();

for (const word of words) {
  trie.addWord(word);
}
```

We'll also have a `result` array to add the words that are in `board`:

```ts
let result: string[] = [];
```

This array will be modified by the function that does the depth-first search, so that at the end of our main function `findWords`, we can just return it.

For each cell, we'll run a depth-first search _if that character is the start of a word in `words`_:

```ts
for (let i = 0; i < rowsLength; i++) {
  for (let j = 0; j < colsLength; j++) {
    if (trie.root.children.has(board[i][j])) {
      dfs(i, j, trie.root.children.get(board[i][j]) as TrieNode, []);
    }
  }
}
```

So, if `board[i][j]` (which is the current character) is the first character of a word in `words`, we'll run `dfs`, passing it the arguments of the current row and column, as well as the next character (`trie.root.children.get(board[i][j])`). We'll also pass it an empty array to keep track of the path we're exploring.

Now let's look at the `dfs` function itself.
The first thing we need to do is to add the current character (the current cell) to our path, and mark it as "visited." We can mark it with an asterisk (`*`) to do that:

```ts
let currentChar = board[currentRow][currentCol];
path.push(currentChar);
board[currentRow][currentCol] = '*';
```

Now, if the current node we're looking at is the end character of a word, that means our `path` consists of all the letters of a word in `words`, so we can add it to `result` as a string. After that, we'll mark that node as _not the end of a word_, because in our next iterations, that node might not be the end character of another word:

```ts
if (currentNode.isEndOfWord) {
  result.push(path.join(''));
  currentNode.isEndOfWord = false;
}
```

From that current cell, we'll look at all the directions we can go as long as we stay within the bounds of `board`, and that next character is _the_ next character in that word (if it's a child node of the current node):

```ts
// Coordinations to go right, left, down, and up
let coords = [[0, 1], [0, -1], [1, 0], [-1, 0]];
for (const [r, c] of coords) {
  let [rowToGo, colToGo] = [currentRow + r, currentCol + c];

  if (!outOfBounds(rowToGo, colToGo) && currentNode.children.has(board[rowToGo][colToGo])) {
    dfs(
      rowToGo,
      colToGo,
      currentNode.children.get(board[rowToGo][colToGo]) as TrieNode,
      path
    );
  }
}
```

Once we have done exploring our options, we need to backtrack, so we need to pop the last character from our `path` and reset the cell to its original character:

```ts
path.pop();
board[currentRow][currentCol] = currentChar;
```

And, that's pretty much it for the `dfs` function:

```ts
function dfs(currentRow: number, currentCol: number, currentNode: TrieNode, path: string[]) {
  let currentChar = board[currentRow][currentCol];
  path.push(currentChar);
  board[currentRow][currentCol] = '*';

  // If we find a word, we'll add it to result, and
  // mark that node as not the end character
  // because it might be in another word
  if (currentNode.isEndOfWord) {
    result.push(path.join(''));
    currentNode.isEndOfWord = false;
  }

  // Coordinations to go right, left, down, and up
  let coords = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  for (const [r, c] of coords) {
    let [rowToGo, colToGo] = [currentRow + r, currentCol + c];

    if (!outOfBounds(rowToGo, colToGo) && currentNode.children.has(board[rowToGo][colToGo])) {
      dfs(
        rowToGo,
        colToGo,
        currentNode.children.get(board[rowToGo][colToGo]) as TrieNode,
        path
      );
    }
  }

  path.pop();
  board[currentRow][currentCol] = currentChar;
}
```

And, the whole solution looks like this:

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

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

class Trie {
  public root: TrieNode;

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

  addWord(word: string) {
    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;
  }
}

function findWords(board: string[][], words: string[]): string[] {
  const rowsLength = board.length;
  const colsLength = board[0].length;

  function outOfBounds(r: number, c: number) {
    return r < 0 || c < 0 || r >= rowsLength || c >= colsLength;
  }

  let result: string[] = [];
  let trie = new Trie();

  for (const word of words) {
    trie.addWord(word);
  }

  function dfs(currentRow: number, currentCol: number, currentNode: TrieNode, path: string[]) {
    let currentChar = board[currentRow][currentCol];
    path.push(currentChar);
    board[currentRow][currentCol] = '*';

    // If we find a word, we'll add it to result, and
    // mark that node as not the end character
    // because it might be in another word
    if (currentNode.isEndOfWord) {
      result.push(path.join(''));
      currentNode.isEndOfWord = false;
    }

    // Coordinations to go right, left, down, and up
    let coords = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    for (const [r, c] of coords) {
      let [rowToGo, colToGo] = [currentRow + r, currentCol + c];

      if (!outOfBounds(rowToGo, colToGo) && currentNode.children.has(board[rowToGo][colToGo])) {
        dfs(
          rowToGo,
          colToGo,
          currentNode.children.get(board[rowToGo][colToGo]) as TrieNode,
          path
        );
      }
    }

    path.pop();
    board[currentRow][currentCol] = currentChar;
  }

  for (let i = 0; i < rowsLength; i++) {
    for (let j = 0; j < colsLength; j++) {
      if (trie.root.children.has(board[i][j])) {
        dfs(i, j, trie.root.children.get(board[i][j]) as TrieNode, []);
      }
    }
  }

  return result;
}
```

#### Time and space complexity

The time complexity of `findWords` can be, in the worst case, {% katex inline %} O(m * n * w) {% endkatex %} where {% katex inline %} m {% endkatex %} is the length of rows, {% katex inline %} n {% endkatex %} is the length of columns, and {% katex inline %} w {% endkatex %} is the total number of words — because we might explore all the cells searching for each word. 

For the space complexity, first, we have our trie whose storage needs will grow as the total number of characters in `words` grow. We can say that it's {% katex inline %} O(s) {% endkatex %} where {% katex inline %} s {% endkatex %} is the number of all characters in `words`. We also store a `path` array in our depth-first search, in the worst case where we need to store every unique cell, we'll end up storing the whole board, so it can have {% katex inline %} O(m * n) {% endkatex %} space complexity where {% katex inline %} m {% endkatex %} is the length of rows and {% katex inline %} n {% endkatex %} is the length of columns.
Combining them together, I think, the space complexity might end up being {% katex inline %} O(s + m * n) {% endkatex %}.

---

If some of the parts still doesn't make sense, that's okay. This is a very, _very_ tough problem, and honestly, backtracking is one of the most challenging concepts that's somewhat easy to wrap your mind around theoretically, but not so easy in practice.

Now that we're done with this chapter as well, it's time for another deep breath. 
Next up, we'll take a look at the graph data structure. Until then, happy coding.