WordSearch

Question

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

Solution

Similar idea to WordSearch II, but however this time we need to return from the code. Remember that we need to pop out the letter that we used as explained in WordSearch II > Gotcha.

[!important]
There might be some gotcha in Happy condition first before failure. In here just remember to return the happy condition first before return False

Implementation

import unittest
from typing import *

class App:
    def exist(self, board: List[List[str]], word: str) -> bool:
        for row in range(len(board)):
            for col in range(len(board[0])):
                if (self.searchWord(board, row, col, word, 0, [])):
                    return True

        return False

    def searchWord(self, board, row, col, word, index, visited):
        if index >= len(word):
            return True

        if not self.isValidCell(board, row, col, visited): 
            return False

        currentLetter = board[row][col] 
        if currentLetter != word[index]: return False
        
        visited.append((row, col))

        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nextRow, nextCol = row + dr, col + dc
            if (self.searchWord(board, nextRow, nextCol, word, index + 1, visited)):
                return True

        visited.pop()
    
    def isValidCell(self, board, row, col, visited):
        return not (row < 0 or col < 0 or row >= len(board) or col >= len(board[0])) and \
                (row, col) not in visited

Time complexity: $O(row \times col \times w)$ for $w$ is the length of word.
Space complexity: $O(1)$ — we keep track of visited but we pop out as we go.

Optimisation

We can replace the visited list with marking the cell as # to reuse the same array.