How hard is LeetCode 212. Word Search II?

LeetCode 212. Word Search II is rated Hard on LeetCode.

What topics does LeetCode 212. Word Search II cover?

LeetCode 212. Word Search II is tagged Trie, Array, String, Backtracking and Matrix on LeetCode.

Word Search II — LeetCode 212 Python Solution

HardTrieArrayStringBacktrackingMatrix

Problem: #212
Pattern: Trie
Reading time: 7 min
Source: leetcode.com

The problem

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.

Example

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

Python solution

Python

class Trie:
    def __init__(self):
        self.children: List[Trie | None] = [None] * 26
        self.ref: int = -1

    def insert(self, w: str, ref: int):
        node = self
        for c in w:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.ref = ref


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        def dfs(node: Trie, i: int, j: int):
            idx = ord(board[i][j]) - ord('a')
            if node.children[idx] is None:
                return
            node = node.children[idx]
            if node.ref >= 0:
                ans.append(words[node.ref])
                node.ref = -1
            c = board[i][j]
            board[i][j] = '#'
            for a, b in pairwise((-1, 0, 1, 0, -1)):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and board[x][y] != '#':
                    dfs(node, x, y)
            board[i][j] = c

        tree = Trie()
        for i, w in enumerate(words):
            tree.insert(w, i)
        m, n = len(board), len(board[0])
        ans = []
        for i in range(m):
            for j in range(n):
                dfs(tree, i, j)
        return ans

Complexity

Measure	Complexity
Time	Exponential (worst case)
Space	O(depth) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 212. Word Search II is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

On study lists

This problem is on Blind 75, NeetCode 150 and Top Interview 150.

Frequently asked questions

How hard is LeetCode 212. Word Search II?: LeetCode 212. Word Search II is rated Hard on LeetCode.
What topics does LeetCode 212. Word Search II cover?: LeetCode 212. Word Search II is tagged Trie, Array, String, Backtracking and Matrix on LeetCode.