Word Search II

LeetCode

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.

Initial attempt

Time spent: 2h 4m | Runtime: 25.73% | Memory: 59.18%

• I originally did not think to build a trie. My original algorithm iterated over the words and tried to find each of them based on initial coordinates.
• After looking at the solution outline, I stored visited nodes in a separate set which resulted in TLE. The actual solution mutates the input.

Solution

• Build a trie from the words.
• Go through each position on the board while traversing the trie.

Cleaned up code

Time spent: 18m | Runtime: 42.87% | Memory: 86.23%

class Solution:
    # Only need to create this once.
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    def findWords(self, board, words):
        # Build trie.
        trie_root = {}
        for word in words:
            node = trie_root
            for character in word:
                node[character] = node.get(character, {})
                node = node[character]
            node['is_word'] = True

        # Explore board.
        found_words = set()
        for i in range(len(board)):
            for j in range(len(board[0])):
                self.explore(board, i, j, trie_root, found_words)
        return list(found_words)

    def explore(self, board, i, j, parent, found_words, current_word=''):
        # Needed for backtrack value restoration.
        character = board[i][j]
        if current_node := parent.get(character):
            current_word += character
            if current_node.get('is_word', False):
                found_words.add(current_word)
            board[i][j] = '#'
            for di, dj in self.directions:
                if (
                    (0 <= i + di < len(board))
                    and (0 <= j + dj < len(board[0]))
                    and (board[i + di][j + dj] in current_node)
                ):
                    self.explore(
                        board, i + di, j + dj,
                        current_node, found_words, current_word,
                    )
            board[i][j] = character

Areas of improvement

• Might be faster if implemented iteratively.