79. Word Search

Problem

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can 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.

https://leetcode.com/problems/word-search/

Example 1:

case1

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

case2

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

case3

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

Test Cases

1 2	class Solution: def exist(self, board: List[List[str]], word: str) -> bool:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('board, word, expected', [
    (
        [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]],
        "ABCCED",
        True
    ),
    (
        [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]],
        "SEE",
        True
    ),
    (
        [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]],
        "ABCB",
        False
    ),

    (
        [['x', 'A', 'D'], ['A', 'B', 'C']],
        'ABCDA',
        True
    ),
    (
        [['x', 'A', 'D'], ['x', 'B', 'C']],
        'ABCDA',
        False
    ),
])
class Test:
    def test_solution(self, board, word, expected):
        sol = Solution()
        assert sol.exist(board, word) == expected

Thoughts

直接递归回溯。

从值等于 word[0] 的 cell 开始，看上下左右四个，对每个等于 word[1] 的 cell 递归处理。

为了避免同一个 cell 被使用多次，可以用一个集合记录当前用到的 cells 的坐标，递归的时候判定是否已经用过了。也可以临时把用到的 cell 的值设置为一个非法值（如空字符串），避免再次被匹配上，注意检查完要还原回去。

设 word 的长度为 w，时间复杂度为 O(m * n * 4ʷ)，空间复杂度 O(w)（递归调用深度）。

Code

solution.py

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])
        w = len(word)
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def find(r: int, c: int, k: int) -> bool:
            if not (0 <= r < m and 0 <= c < n and board[r][c] == word[k]):
                return False
            if k == w - 1:
                return True

            backup = board[r][c]
            board[r][c] = '' # Avoid reuse the same cell.
            found = any(find(r + dr, c + dc, k + 1) for dr, dc in dirs)
            board[r][c] = backup
            return found

        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0] and find(i, j, 0):
                    return True

        return False