LeetCode 101: 79 Word Search

LeetCode Problem: 79. Word Search

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

Problem Description:

Given an m x n grid of characters 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

Original Code (Depth-First Search Approach):

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        r = len(board)  # Get the number of rows
        c = len(board[0])  # Get the number of columns

        def dfs(board, word, idx, i, j, r, c):
            if i < 0 or i >= r or j < 0 or j >= c or board[i][j] != word[idx]:  # Check boundaries and current character
                return False
            if idx == len(word) - 1:  # If we found the last character
                return True

            board[i][j] = '#'  # Mark the cell as visited

            # Explore all four possible directions (up, down, left, right)
            if (dfs(board, word, idx + 1, i - 1, j, r, c) or
                dfs(board, word, idx + 1, i + 1, j, r, c) or
                dfs(board, word, idx + 1, i, j - 1, r, c) or
                dfs(board, word, idx + 1, i, j + 1, r, c)):
                return True

            board[i][j] = word[idx]  # Restore the original character
            return False  # Word not found in this path

        for i in range(r):  # Iterate through each cell in the grid
            for j in range(c):
                if dfs(board, word, 0, i, j, r, c):  # Start DFS from each cell
                    return True

        return False  # If no path found

Line-by-Line Explanation and Example Execution:

def exist(self, board: List[List[str]], word: str) -> bool:
- Defines the main function exist, which accepts a 2D grid (board) and a string (word) and returns whether the word exists in the grid.
r = len(board)
- Gets the number of rows in the grid.
c = len(board[0])
- Gets the number of columns in the grid.
def dfs(board, word, idx, i, j, r, c):
- Defines a nested helper function dfs that performs depth-first search starting from cell (i, j) with the current index idx in the word.
if i < 0 or i >= r or j < 0 or j >= c or board[i][j] != word[idx]:
- Checks if the current position is out of bounds or if the current cell does not match the corresponding character in the word. If any condition is true, return False.
if idx == len(word) - 1:
- Checks if we have found the last character of the word. If so, returns True.
board[i][j] = '#'
- Marks the current cell as visited by changing its value to a special character ('#').

Recursive Calls:

Explores all four possible directions (up, down, left, right):

if (dfs(board, word, idx + 1, i - 1, j, r, c) or
dfs(board, word, idx + 1, i + 1, j, r, c) or
dfs(board, word, idx + 1, i, j - 1, r, c) or
dfs(board, word, idx + 1, i, j + 1, r, c)):
return True

board[i][j] = word[idx]
- Restores the original character of the cell after exploring all possibilities.
return False
- Returns False if the word cannot be formed starting from the current cell.

Outer Loop:

Iterates through each cell in the grid:

for i in range(r):  # Iterate through each row
for j in range(c):  # Iterate through each column
    if dfs(board, word, 0, i, j, r, c):  # Start DFS from each cell
        return True

return False
- If no path is found after checking all cells, returns False.

Example Execution:

Assuming we have the following grid and word:

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

Execution steps:

Initial Call:
- Call dfs(board, word, 0, 0, 0, 3) to start searching from the top-left corner.
DFS Process:
- At (0, 0), the character is ‘A’, which matches word[0]. Mark (0, 0) as visited.
- Move to (0, 1), the character is ‘B’, which matches word[1]. Mark (0, 1) as visited.
- Move to (0, 2), the character is ‘C’, which matches word[2]. Mark (0, 2) as visited.
- Move to (1, 2), the character is ‘C’, which matches word[3]. Mark (1, 2) as visited.
- Move to (2, 2), the character is ‘E’, which matches word[4]. Mark (2, 2) as visited.
- Finally, move to (2, 1), the character is ‘D’, which matches word[5]. Mark (2, 1) as visited.
Final Result:
- The word "ABCCED" is found, so the function returns True.

Time Complexity Analysis:

Time Complexity: O(m * n)
- Where m is the number of rows and n is the number of columns. Each cell is visited once.

Space Complexity Analysis:

Space Complexity: O(m * n)
- In the worst case, the recursion stack could grow to the size of the grid.

Tips and Warnings:

Edge Cases:
- Consider cases where the board is empty or contains only one character.
Understanding DFS:
- Make sure to understand how depth-first search explores the grid.
Cell Visit Restoration:
- Remember to restore the cell’s original value after the DFS completes to avoid affecting subsequent searches.

Optimized Code Example Using Hash Table (Optional):

This problem is typically implemented using DFS, but to enhance efficiency, you can manage state better with the visited nodes. The above code is already efficient but does not require further optimizations.

Summary

DFS Method: Effectively finds whether a word exists in a 2D grid, with a time complexity of O(m n) and a space complexity of O(m n).
Clear and Understandable: The code is straightforward and easy to understand, suitable for handling this type of problem.

Application Tips

Choose Appropriate Methods:
- Select the method best suited to specific problem requirements to ensure efficiency and readability.
Handle Edge Cases:
- Always consider edge cases in algorithm design to avoid potential errors.
Optimize Space Usage:
- When handling large datasets, consider using space-efficient algorithms.

Post Views: 33

CODEBITWAVE