LC 79

Solution to LeetCode 79 Word Search.

LeetCode 79

Word Search (Medium). [link]

Backtracking and DFS. Time complexity for the function search is O(4^l), where l = len(word). The total complexity is O(m*n*4^l). The space complexity is O(m*n + l).

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        def search(board, word, depth, ii, jj):
            if ii < 0 or ii == w or jj < 0 or jj == h or word[depth] != board[jj][ii]:
                return False # if it is out of boundary
            if depth == len(word) - 1: # if the depth reaches the final char
                return True
            
            cur = board[jj][ii]
            board[jj][ii] = 0 # make sure it will not be searched twice
            found = search(board, word, depth+1, ii+1, jj) or search(board, word, depth+1, ii-1, jj) or search(board, word, depth+1, ii, jj+1) or search(board, word, depth+1, ii, jj-1)
            board[jj][ii] = cur
            return found
        
        h = len(board)
        w = len(board[0])
        if h == 0 or w == 0:
            return False
        for i in range(w):
            for j in range(h):
                if search(board, word, 0, i, j):
                    return True
        return False