Solution 1: Using Trie

Intuition:

To solve this problem efficiently, we can use a Trie data structure along with backtracking. We’ll first construct a Trie from the given list of words. Then, we’ll perform a depth-first search (DFS) on the board, starting from each cell. During the DFS traversal, we’ll check if the current prefix formed by the visited cells exists in the Trie. If it does, we’ll continue the DFS and check if we’ve found a complete word. If a complete word is found, we’ll add it to the result list.

Solution:

from typing import List

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

def find_words(board: List[List[str]], words: List[str]) -> List[str]:
    # Initialize Trie and result list
    trie = Trie()
    result = []

    # Construct Trie from the list of words
    for word in words:
        trie.insert(word)
    
    # Helper function for DFS traversal
    def dfs(node, i, j, path):
        if node.is_end:
            result.append(path)
            node.is_end = False  # Mark word as visited to avoid duplicates
        
        # Check boundaries and visited cells
        if 0 <= i < len(board) and 0 <= j < len(board[0]) and board[i][j] in node.children:
            char = board[i][j]
            board[i][j] = '#'  # Mark cell as visited
            
            # Recursively explore adjacent cells
            dfs(node.children[char], i+1, j, path + char)
            dfs(node.children[char], i-1, j, path + char)
            dfs(node.children[char], i, j+1, path + char)
            dfs(node.children[char], i, j-1, path + char)
            
            board[i][j] = char  # Reset cell to its original value after backtracking

    # Start DFS from each cell on the board
    for i in range(len(board)):
        for j in range(len(board[0])):
            dfs(trie.root, i, j, '')
    
    return result

# Test case
board = [
    ['o','a','a','n'],
    ['e','t','a','e'],
    ['i','h','k','r'],
    ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

print(find_words(board, words))  # Output: ["oath", "eat"]

Time Complexity:

  • Let n be the number of cells in the board and m be the number of words.
  • Constructing the Trie takes O(m * word_length) time.
  • Each DFS traversal starting from a cell has a worst-case time complexity of O(4^word_length), where word_length is the maximum length of the words.
  • Since we perform DFS starting from each cell in the board, the overall time complexity is O(n * 4^word_length).

Space Complexity:

  • The space complexity is dominated by the Trie data structure, which requires O(m * word_length) space.
  • Additionally, the space used by the recursion stack during DFS traversal is O(word_length).
  • Therefore, the overall space complexity is O(m * word_length).

Solution 2: Without Using Trie

Intuition:

An alternative approach to solve this problem is by using a backtracking algorithm without constructing a Trie data structure. In this approach, we can directly search for each word in the list within the board using backtracking.

Here’s a high-level overview of the alternative solution:

  1. Iterate through each word in the list.
  2. For each word, iterate through each cell in the board to find the starting cell that matches the first character of the word.
  3. Once a matching starting cell is found, perform a depth-first search (DFS) starting from that cell to check if the word can be formed by traversing adjacent cells.
  4. During the DFS, keep track of the visited cells to avoid using the same cell more than once in a word.
  5. If the word is found, add it to the result list.

This approach eliminates the need to construct a Trie data structure, resulting in potentially simpler implementation. However, it may be less efficient compared to using a Trie, especially for large word lists or boards with many cells.

Solution:

from typing import List

def find_words(board: List[List[str]], words: List[str]) -> List[str]:
    if not board or not board[0] or not words:
        return []

    def dfs(i, j, word):
        # Base case: If the word is empty, it means all characters are found
        if len(word) == 0:
            return True
        
        # Check boundaries and if the current cell matches the first character of the word
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[0]:
            return False

        # Temporarily mark the current cell as visited
        temp, board[i][j] = board[i][j], '#'
        
        # Recursively search in all four directions
        found = dfs(i + 1, j, word[1:]) or dfs(i - 1, j, word[1:]) or dfs(i, j + 1, word[1:]) or dfs(i, j - 1, word[1:])
        
        # Restore the original value of the cell
        board[i][j] = temp
        return found

    result = []
    # Iterate through each word in the list
    for word in words:
        found = False
        # Iterate through each cell in the board to start the DFS search
        for i in range(len(board)):
            for j in range(len(board[0])):
                # If the word is found, add it to the result list
                if dfs(i, j, word):
                    result.append(word)
                    found = True
                    break
            if found:
                break

    return result

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

print(find_words(board, words))  # Output: ["oath", "eat"]

Time Complexity:

  • Let n be the number of cells in the board and m be the number of words.
  • For each word in the list, we perform a DFS search starting from each cell in the board. The worst-case time complexity of each DFS traversal is O(4^word_length), where word_length is the length of the word.
  • Therefore, the overall time complexity of the solution is O(n * m * 4^word_length).

Space Complexity:

  • The space complexity is dominated by the recursion stack during DFS traversal, which can go up to O(word_length) depth.
  • Additionally, the space used by the temporary variable temp is constant.
  • Therefore, the overall space complexity is O(word_length) due to recursion stack space.