79. Word Search

Solution 1: DFS

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board:
            return False
        
        def dfs(idxRestWord, xAxis, yAxis):
            # Compare success
            if idxRestWord == len(word):
                return True
            # Check overflow
            if (xAxis < 0 or yAxis < 0) or (xAxis >= len(board) or yAxis >= len(board[0])):
                return False
            
            # Compare search pattern
            if board[xAxis][yAxis] != word[idxRestWord]:
                return False
            
            # Temporarily mark the char to avoid duplicated search
            board[xAxis][yAxis] = '*'
            
            nextIdx = idxRestWord + 1
            srchResFromHere = (
                dfs(nextIdx, xAxis + 1, yAxis) or
                dfs(nextIdx, xAxis, yAxis + 1) or 
                dfs(nextIdx, xAxis - 1, yAxis) or 
                dfs(nextIdx, xAxis, yAxis - 1)
            )
                
            # Restore the board back (For future search)
            board[xAxis][yAxis] = word[idxRestWord]
            return srchResFromHere
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                srchResult = dfs(0, i, j)
                if srchResult:
                    return True
        return False

Time Complexity: O(MN) // Traverse the whole board at most
Space Complexity: O(Min( MN, len(word) )) // Worst case DFS the whole board

Reference

https://leetcode.com/problems/word-search/discuss/2843530/Python3-Backtracking-(Not-TLE)-for-beginners-only!
https://leetcode.com/problems/word-search/discuss/27658/Accepted-very-short-Java-solution.-No-additional-space.

Follow-up: Word Search II