Word Search II hard

Problem Statement

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 connected. The same letter cell may not be used more than once in a word.

Example 1

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

Example 2

Input: board = [["a","b"],["c","d"]], words = ["abcb"] Output: []

Steps

1. Trie Data Structure: Build a Trie (prefix tree) from the list of words. A Trie efficiently stores and searches for words based on prefixes. Each node in the Trie represents a character, and paths from the root to leaf nodes represent words.

2. Depth-First Search (DFS): Perform a DFS on the board. For each cell, explore all possible paths starting from that cell. As we explore a path, we concurrently traverse the Trie.

3. Trie Traversal and Word Discovery: If a path's character sequence matches a prefix in the Trie, we continue the DFS. If a path's character sequence reaches a leaf node in the Trie, we've found a word, add it to the result set (ensuring we don't add duplicates).

4. Backtracking: After exploring a path, backtrack to the previous cell to explore other paths from that cell. This ensures we don't reuse cells within a word.

5. Optimization: Mark visited cells during DFS to avoid cycles and redundant searches.

Explanation

The Trie significantly optimizes the search. Instead of searching for each word individually, we perform one comprehensive search using the Trie to check for prefixes. DFS efficiently explores all possible word formations on the board, and backtracking guarantees we examine all possibilities without repetition.

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = 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_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_word


def findWords(board, words):
    trie = Trie()
    for word in words:
        trie.insert(word)

    m, n = len(board), len(board[0])
    result = set()

    def dfs(row, col, node, word):
        if row < 0 or row >= m or col < 0 or col >= n or (row, col) in visited:
            return
        
        char = board[row][col]
        if char not in node.children:
            return

        visited.add((row, col))
        node = node.children[char]
        word += char
        
        if node.is_word:
            result.add(word)

        dfs(row + 1, col, node, word)
        dfs(row - 1, col, node, word)
        dfs(row, col + 1, node, word)
        dfs(row, col - 1, node, word)
        visited.remove((row, col))

    visited = set()
    for r in range(m):
        for c in range(n):
            dfs(r, c, trie.root, "")

    return list(result)

Complexity

• Time Complexity: O(M * N * 4^L), where M and N are the dimensions of the board, and L is the maximum length of a word. In the worst case, we explore all possible paths on the board.
• Space Complexity: O(M * N + sum of word lengths). This accounts for the space used by the board, visited set, and Trie. The Trie's space is proportional to the total length of all words.