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×j∗n)O(i \times j * n)
    Where ii is the number of rows in the board, jj is the number of columns in the board and nn 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)O(n) where nn is the number of characters in the words list.

  • Space: O(n)O(n)
    Where nn 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.