Word Search Python Solution with Tests

Tested Python solution for LeetCode 79 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 79, Medium. Topics: Array, String, Backtracking, Depth-First Search, Matrix. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

lcpy gen -n 79   # by problem number
lcpy gen -s word_search   # by problem name

​

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.

​

Examples

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

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

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?

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import Counter


class Solution:
    # Time: O(m*n*4^L) where L is word length
    # Space: O(L)
    def exist(self, board: list[list[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        # Early pruning: check if board has enough characters
        board_counter = Counter(ch for row in board for ch in row)
        word_counter = Counter(word)
        for ch in word_counter:
            if board_counter[ch] < word_counter[ch]:
                return False

        # Optimization: start from less frequent end
        if board_counter[word[0]] > board_counter[word[-1]]:
            word = word[::-1]

        def dfs(i: int, j: int, k: int) -> bool:
            if k == len(word):
                return True
            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
                return False

            temp = board[i][j]
            board[i][j] = "#"
            for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                if dfs(i + di, j + dj, k + 1):
                    board[i][j] = temp
                    return True
            board[i][j] = temp
            return False

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

​

Complexity

Time	Space
O(mn4^L) where L is word length	O(L)

​

Tags

Grind 75, Grind, Blind 75, NeetCode 150, NeetCode 250, NeetCode All.