Introduction

In this blog post, we will explore how to solve the LeetCode problem "79" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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?

Explanation

Here's an efficient solution to the word search problem:

• DFS Traversal with Backtracking: The core idea is to perform a Depth-First Search (DFS) starting from each cell in the grid. For each cell, we check if it matches the first character of the word. If it does, we recursively explore its neighbors (up, down, left, right) to see if the remaining characters of the word can be found. Backtracking is used to undo the choice of a cell if it leads to a dead end.
• Visited Set to Avoid Cycles: To prevent revisiting the same cell during a single word search, we use a set visited to keep track of the cells that have already been explored in the current path.

• Early Termination: The search terminates as soon as the word is found. Also, if the current cell does not match the character being searched or the search goes out of bounds, that path is terminated immediately.

• Time Complexity: O(m n 3^L), where m is the number of rows, n is the number of columns, and L is the length of the word. In the worst case, each cell could be the starting point, and from each cell, we explore up to 3 unvisited neighbors for each character in the word. Space Complexity: O(L), due to the recursion depth of the DFS, where L is the length of the word, and the visited set.

Code

    class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        visited = set()

        def dfs(row, col, i):
            if i == len(word):
                return True

            if (row < 0 or row >= rows or col < 0 or col >= cols or
                board[row][col] != word[i] or (row, col) in visited):
                return False

            visited.add((row, col))
            # Explore all 4 possible directions
            found = (dfs(row + 1, col, i + 1) or
                     dfs(row - 1, col, i + 1) or
                     dfs(row, col + 1, i + 1) or
                     dfs(row, col - 1, i + 1))

            visited.remove((row, col))  # Backtrack
            return found

        for row in range(rows):
            for col in range(cols):
                if dfs(row, col, 0):
                    return True

        return False