Skip to main content
CodeEasy v0.1

Word Search II

Hard Subject: Tries
Time Complexity
O(M * N * 4^L)
Space Complexity
O(L)

Problem Description

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 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"]

Optimal Solution

Python

Approach: Trie + Backtracking

Insert all words into a Trie. For each cell on the board, trigger a backtracking DFS if the character exists in the root Trie node's children. During DFS, mark the cell as visited (e.g., with #), traverse the Trie, and if an end of word is reached, add it to the result. Remove word from Trie to avoid duplicates.

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

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = TrieNode()
        for w in words:
            node = root
            for c in w:
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
            node.is_end = True

        res = set()
        rows, cols = len(board), len(board[0])

        def dfs(r, c, node, word):
            if (r < 0 or c < 0 or r >= rows or c >= cols or 
                board[r][c] not in node.children):
                return

            char = board[r][c]
            board[r][c] = '#'
            node = node.children[char]
            if node.is_end:
                res.add(word + char)

            dfs(r+1, c, node, word + char)
            dfs(r-1, c, node, word + char)
            dfs(r, c+1, node, word + char)
            dfs(r, c-1, node, word + char)

            board[r][c] = char

        for r in range(rows):
            for c in range(cols):
                dfs(r, c, root, "")

        return list(res)