Word Search Ii - Leetcode Solution

Problem Statement:

Given an m x n grid of words board and a list of 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.

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: []

Approach:

The problem can be solved using the Trie data structure (Trie is a tree-like data structure that stores a dynamic set of strings). We create a Trie from the list of words provided in the input. Once we have the Trie, we can search for all valid words on the board by traversing the board and Trie simultaneously.

Steps:

1. Create a Trie from the list of words given in the input. Each node of the Trie will store:
   • the character at the current node
   • a boolean flag to indicate whether the current node represents the end of a word from the input list
   • a list of children nodes
2. Traverse the board and for each cell in the board, search for all valid words that can be formed starting from that cell.
   • For each cell in the board, perform a depth-first traversal, following all possible paths that can be formed starting from that cell on the board.
   • If at any point during the traversal, we reach a dead end (i.e., the current path does not match any word in the Trie), we backtrack and explore other possible paths.
   • If we reach a Trie node that represents the end of a word from the input list, add that word to the final list of valid words.
3. Return the final list of valid words.

Code:

Here is the Python code to solve the Word Search II problem using the Trie data structure:

class TrieNode: def init(self): self.char = None self.end_of_word = False self.children = {}

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

def add_word(self, word):
    current_node = self.root
    for char in word:
        if char not in current_node.children:
            current_node.children[char] = TrieNode()
        current_node = current_node.children[char]
    current_node.end_of_word = True

class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: if not board or not words: return [] trie = Trie() for word in words: trie.add_word(word) m, n = len(board), len(board[0]) visited = set() res = set()

    def dfs(i, j, current_node, prefix):
        # check if current node is end of a word
        if current_node.end_of_word:
            res.add(prefix)
        # mark current cell as visited
        visited.add((i, j))
        # explore all possible paths from the current cell
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            x, y = i + dx, j + dy
            # check if new cell is within bounds and not visited already
            if 0 <= x < m and 0 <= y < n and (x, y) not in visited and board[x][y] in current_node.children:
                dfs(x, y, current_node.children[board[x][y]], prefix + board[x][y])
        # backtrack
        visited.remove((i, j))

    for i in range(m):
        for j in range(n):
            if board[i][j] in trie.root.children:
                dfs(i, j, trie.root.children[board[i][j]], board[i][j])

    return list(res)

Time Complexity:

The time complexity of the above solution is O(m x n x 4^k), where m is the number of rows in the board, n is the number of columns in the board, and k is the maximum length of words in the input list. The reason for 4^k is that for each cell in the board, we have at most 4 possible neighbors to explore, and we can explore up to k cells in a single path. Therefore, the worst-case scenario is when all cells in the board are explored, and we have to search for all words of length k in the Trie.

1