s0079_word_search

79. Word Search

Medium

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.

Example 1:

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

Output: true

Example 2:

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

Output: true

Example 3:

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?

To solve this task using Python with a Solution class, you can follow these steps:

1. Define a class named Solution.
2. Inside the class, define a method named exist that takes board and word as input parameters.
3. Implement an algorithm to search for the word in the grid board.
4. Use a backtracking approach to explore all possible paths in the grid to find the word.
5. Create a recursive function named search that takes row, col, index (current character index in the word), and visited (a set of visited cells) as parameters.
6. Base case: If index is equal to the length of the word, return True (word found).
7. If the current cell (board[row][col]) is not equal to the character at index index of the word or the cell is already visited, return False.
8. Mark the current cell as visited by adding (row, col) to the set visited.
9. Recursively call search with the neighboring cells (up, down, left, right) and increment index by 1.
10. If any of the recursive calls return True, return True.
11. After exploring all possible paths from the current cell, backtrack by removing (row, col) from visited.
12. Return False if no path from the current cell leads to finding the word.
13. Iterate through each cell in the grid and call the search function with the starting position and index 0.
14. Return the result of the search function.

Here's the implementation:

class Solution:
    def exist(self, board, word):
        def search(row, col, index, visited):
            if index == len(word):
                return True
            
            if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]) \
                    or board[row][col] != word[index] or (row, col) in visited:
                return False
            
            visited.add((row, col))
            if search(row - 1, col, index + 1, visited) \
                    or search(row + 1, col, index + 1, visited) \
                    or search(row, col - 1, index + 1, visited) \
                    or search(row, col + 1, index + 1, visited):
                return True
            
            visited.remove((row, col))
            return False
        
        for row in range(len(board)):
            for col in range(len(board[0])):
                if search(row, col, 0, set()):
                    return True
        
        return False

# Example usage:
solution = Solution()
board = \[\["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
print(solution.exist(board, "ABCCED"))  # Output: True
print(solution.exist(board, "SEE"))     # Output: True
print(solution.exist(board, "ABCB"))    # Output: False

This solution explores all possible paths in the grid to find the word using backtracking. It efficiently searches for the word, and the time complexity depends on the size of the grid and the length of the word.

Solution

from typing import List
from collections import Counter

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        n = len(board)
        m = len(board[0])
        p = len(word)

        if p > n * m:
            return False

        def is_sub(board, word):
            c = Counter()
            for line in board:
                c.update(line)
            w = Counter(word)
            return all(c[ch] >= count for ch, count in w.items())

        if not is_sub(board, word):
            return False

        def rec(i, j, k, visited):
            if k == p:
                return True

            for ii, jj in ((i - 1, j),
                           (i + 1, j),
                           (i, j - 1),
                           (i, j + 1)):
                if (
                    0 <= ii < n
                    and 0 <= jj < m
                    and (ii, jj) not in visited
                    and word[k] == board[ii][jj]
                ):
                    visited.add((ii, jj))
                    if rec(ii, jj, k + 1, visited):
                        return True
                    visited.remove((ii, jj))
            return False

        for i, line in enumerate(board):
            for j, elem in enumerate(line):
                if elem == word[0] and rec(i, j, 1, {(i, j)}):
                    return True
        return False