Problem Statement in English

You’re given a 2D board board, and a list of words, words. You need to find all the words in the list that can be formed by a sequence of adjacent characters in the board.

Approach

You need to know what a trie is. Check this problem out if not.

The mistake I made was adding the entire board to the trie. This is not needed. We only need to add words to the trie. In fact doing this will give you a TLE (Time Limit Exceeded).

From there the next thing you need to do is search through the trie with each cell in the board as a starting point. If you find a word, add it to the result set and remove it from the trie.

Removing the word from the trie can result in upto a 7x speedup (trust me, I figured this out the hard way). It’s quite dramatic really.

Solution in Python


class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.isWord = False
        # while building the trie,
        # everytime we add a character
        # we increment its count by 1
        # 
        # that way, later, we can keep track of
        # how many times a character must be searched 
        # 
        # helps prevent duplicate searches
        self.count = 0


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()

        # stores words that are in the grid and trie
        res: set[str] = set()

        # stores the indexes that have been seen
        seen: set[tuple[int, int]] = set()

        # remove `word` from the trie
        def removeWord(word):
            ptr = root

            for c in word:
                if c in ptr.children:
                    ptr = ptr.children[c]
                    ptr.count -= 1

            # mark the node as not a word
            # as we've already found it
            ptr.isWord = False

        # add `word` to the trie
        def addWord(word):
            node = root
            
            for char in word:
                if char not in node.children:
                    temp = TrieNode()
                    node.children[char] = temp

                # move the pointer forward
                node = node.children[char]
                # increment the count of the node
                node.count += 1

            # mark the the node 
            # as the end of a word
            node.isWord = True

        # Build trie from words
        for word in words:
            addWord(word)

        def recursiveCall(
            i: int,
            j: int,
            trieNode: TrieNode,
            word: str,
        ):

            if (
                i not in range(len(board))
                or j not in range(len(board[i]))
                or (i, j) in seen
                or board[i][j] not in trieNode.children
                or trieNode.children[board[i][j]].count < 1
            ):
                return
            else:
                # the character we're currently looking at
                # in the board
                character = board[i][j]

                # move the pointer forward
                trieNode = trieNode.children[character]
                # add the character to the word we're currently forming
                word += character

                # if we've reached a node
                # that marks the end of a word
                # add it to the result set
                #
                # and remove the word from the trie
                # so that we don't check for it again
                if trieNode.isWord:
                    res.add(word)
                    removeWord(word)

                # mark this index as seen
                seen.add((i, j))

                # left cell
                recursiveCall(i - 1, j, trieNode, word)
                # right cell
                recursiveCall(i + 1, j, trieNode, word)
                # bottom cell
                recursiveCall(i, j - 1, trieNode, word)
                # top cell
                recursiveCall(i, j + 1, trieNode, word)

                # mark this index as unseen
                # so that we can reuse the same set
                # in the future
                seen.remove((i, j))

        for row in range(len(board)):
            for col in range(len(board[row])):
                # for each index in the grid search through the trie
                recursiveCall(row, col, root, "")

        # return the answer
        return list(res)

Complexity

  • Time: $O(i \times j * n)$
    Where $i$ is the number of rows in the board, $j$ is the number of columns in the board and $n$ is the number of characters in the words list.

    This is because for each cell in the board, we search through the trie. The trie search is $O(n)$ where $n$ is the number of characters in the words list.

  • Space: $O(n)$
    Where $n$ number of characters in the words list.

Mistakes I Made

As I mentioned earlier, I added the entire board to the trie. I had to look at the solution to figure out what I was doing wrong.

Further, I didn’t think of removing the word from the trie after finding it. This is a very important step as it can result in a crucial speedup.

And we are done.