LeetCode #212: Word Search II

https://leetcode.com/problems/word-search-ii/

The problem asks us to find all the words from a given list that can be constructed from the characters of the given 2D board. To solve this problem, we can use a Trie data structure which is a tree-like data structure that is often used to store strings. We start by constructing a Trie from the list of words we have been given. We insert each word into the Trie by creating a new node for each character in the word. The last node of the word has a special character $ to indicate the end of the word.

Next, we traverse the 2D board and for each cell that we visit, we check if the character in the cell is present in the Trie. If it is, we move to the next cell and repeat the process. If we find a word in the Trie that ends with the special character $, we add that word to our list of matched words.

We perform the above process recursively for all neighboring cells in the 2D board. We mark the cells that we have already visited by replacing their value with a special character, so we don’t revisit them in future iterations. After we have explored all the paths from a cell, we restore the value of that cell to its original value.

At the end of the process, we return the list of matched words that we have found.

Here is the solution in python3:

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        WORD_KEY = '$'
        
        trie = {}
        for word in words:
            node = trie
            for letter in word:
                # retrieve the next node; If not found, create an empty node.
                node = node.setdefault(letter, {})
            # mark the existence of a word in trie node
            node[WORD_KEY] = word
        
        num_rows = len(board)
        num_cols = len(board[0])
        
        matched_words = []
        
        def backtracking(row, col, parent):    
            
            letter = board[row][col]
            curr_node = parent[letter]
            
            # check if we find a match of word
            word_match = curr_node.pop(WORD_KEY, False)
            if word_match:
                # also we removed the matched word to avoid duplicates,
                # as well as avoiding using set() for results.
                matched_words.append(word_match)
            
            # Before the EXPLORATION, mark the cell as visited 
            board[row][col] = '#'
            
            # Explore the neighbors in 4 directions, i.e. up, right, down, left
            for (row_offset, col_offset) in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                new_row, new_col = row + row_offset, col + col_offset     
                if new_row < 0 or new_row >= num_rows or new_col < 0 or new_col >= num_cols:
                    continue
                if not board[new_row][new_col] in curr_node:
                    continue
                backtracking(new_row, new_col, curr_node)
        
            # End of EXPLORATION, we restore the cell
            board[row][col] = letter
        
            # Optimization: incrementally remove the matched leaf node in Trie.
            if not curr_node:
                parent.pop(letter)

        for row in range(num_rows):
            for col in range(num_cols):
                # starting from each of the cells
                if board[row][col] in trie:
                    backtracking(row, col, trie)
        
        return matched_words

Time and Space Complexity

The time complexity of the solution is determined by the backtracking function, which explores all possible paths in the board. In the worst case scenario, all possible paths have to be explored, leading to a time complexity of O(mn4^k), where m and n are the dimensions of the board, and k is the length of the longest word in the dictionary. The 4^k term arises from the fact that the search can go in 4 different directions for each letter of the word.

The space complexity of the solution is determined by the trie data structure that is built to store the words in the dictionary. The worst-case scenario is that all words in the dictionary have unique prefixes, leading to a space complexity of O(N*K), where N is the total number of words in the dictionary and K is the length of the longest word.

In practice, the space complexity is likely to be much smaller than O(N*K), because many words will share common prefixes, resulting in a much more compact trie data structure.