#212

Word Search II

hard· Triesruns: 0

Given an m x n board of characters and a list of words, return all words that can be found on the board. Each word must be constructed from sequentially adjacent cells (horizontally or vertically), and the same cell may not be used more than once in a single word.

wpm 0acc 100%time 0:000 / 1331

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

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

        rows, cols = len(board), len(board[0])
        result = []

        def dfs(r: int, c: int, node: TrieNode) -> None:
            if (
                r < 0
                or r >= rows
                or c < 0
                or c >= cols
                or board[r][c] not in node.children
            ):
                return
            ch = board[r][c]
            next_node = node.children[ch]
            if next_node.word is not None:
                result.append(next_node.word)
                next_node.word = None
            board[r][c] = "#"
            dfs(r + 1, c, next_node)
            dfs(r - 1, c, next_node)
            dfs(r, c + 1, next_node)
            dfs(r, c - 1, next_node)
            board[r][c] = ch

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

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.