Hard — Trie | Backtracking | DFS | Matrix

The Problem

Given a 2D board of characters and a list of words, find all words from the list that can be formed by sequentially adjacent letters on the board, where each cell can only be used once per word.

Approach

Uses a Trie data structure to store all target words with optimization for word orientation based on character frequency. Performs DFS from each board cell to traverse possible paths while tracking visited cells through backtracking, removing found words from the Trie to avoid duplicates.

Time: O(M * N * 4^L) · Space: O(W * L)

Code

from collections import Counter
from itertools import chain, product
from typing import List

class TrieNode:
    def __init__(self):
        self.children = {}  # Store child nodes for each character
        self.refcnt = 0  # Count of references to this node
        self.is_word = False  # Flag to indicate if a complete word ends at this node
        self.is_rev = False  # Flag to indicate if a word should be reversed

class Trie:
    def __init__(self):
        self.root = TrieNode()  # Initialize the root of the trie

    def insert(self, word, rev):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
            node.refcnt += 1
        node.is_word = True
        node.is_rev = rev

    def remove(self, word):
        node = self.root
        for i, c in enumerate(word):
            parent = node
            node = node.children[c]

            if node.refcnt == 1:
                path = [(parent, c)]
                for c in word[i + 1 :]:
                    path.append((node, c))
                    node = node.children[c]
                for parent, c in path:
                    parent.children.pop(c)
                return
            node.refcnt -= 1
        node.is_word = False

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        res = []
        n, m = len(board), len(board[0])
        trie = Trie()

        # Count characters on the board
        boardcnt = Counter(chain(*board))

        # Insert words into trie with appropriate orientation
        for w, wrdcnt in ((w, Counter(w)) for w in words):
            if any(wrdcnt[c] > boardcnt[c] for c in wrdcnt):
                continue  # Skip if the word cannot be formed from the board
            if wrdcnt[w[0]] < wrdcnt[w[-1]]:
                trie.insert(w, False)
            else:
                trie.insert(w[::-1], True)

        def dfs(r, c, parent) -> None:
            if not (node := parent.children.get(board[r][c])):
                return
            path.append(board[r][c])
            board[r][c] = "#"  # Mark visited cell

            if node.is_word:
                word = "".join(path)
                res.append(word[::-1] if node.is_rev else word)
                trie.remove(word)

            # Explore neighboring cells
            if r > 0:
                dfs(r - 1, c, node)
            if r < n - 1:
                dfs(r + 1, c, node)
            if c > 0:
                dfs(r, c - 1, node)
            if c < m - 1:
                dfs(r, c + 1, node)

            board[r][c] = path.pop()  # Backtrack and unmark cell

        path = []
        for r, c in product(range(n), range(m)):
            dfs(r, c, trie.root)
        return res

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment