79.Word Search

Tags: [dfs], [word], [search], [four_direction]

Com: {fb}

Link: https://leetcode.com/problems/word-search/\#/description

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board=

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word ="ABCCED", -> returns true,

word ="SEE", -> returns true,

word ="ABCB", -> returns false.

Solution: DFS, Four Direction

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if not board or not board[0]:
            return not word
        if not word:
            return True

        num_of_rows = len(board)
        num_of_cols = len(board[0])
        visited = [[False for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]
        for row in xrange(num_of_rows):
            for col in xrange(num_of_cols):
                if board[row][col] != word[0]:
                    continue

                visited[row][col] = True
                if self.exist_helper(word, 1, board, num_of_rows, num_of_cols, row, col, visited):
                    return True
                visited[row][col] = False

        return False

    def exist_helper(self, word, index, board, num_of_rows, num_of_cols, row, col, visited):
        # base case
        if index >= len(word):
            return True

        # check four directions
        # top
        if row - 1 >= 0 and board[row - 1][col] == word[index] and not visited[row - 1][col]:
            visited[row - 1][col] = True
            if self.exist_helper(word, index + 1, board, num_of_rows, num_of_cols, row - 1, col, visited):
                return True
            visited[row - 1][col] = False

        # left
        if col - 1 >= 0 and board[row][col - 1] == word[index] and not visited[row][col - 1]:
            visited[row][col - 1] = True
            if self.exist_helper(word, index + 1, board, num_of_rows, num_of_cols, row, col - 1, visited):
                return True
            visited[row][col - 1] = False

        # bottom
        if row + 1 < num_of_rows and board[row + 1][col] == word[index] and not visited[row + 1][col]:
            visited[row + 1][col] = True
            if self.exist_helper(word, index + 1, board, num_of_rows, num_of_cols, row + 1, col, visited):
                return True
            visited[row + 1][col] = False

        # right
        if col + 1 < num_of_cols and board[row][col + 1] == word[index] and not visited[row][col + 1]:
            visited[row][col + 1] = True
            if self.exist_helper(word, index + 1, board, num_of_rows, num_of_cols, row, col + 1, visited):
                return True
            visited[row][col + 1] = False

        return False

Note:

• Time complexity = O(num_of_rows * num_of_cols * num_of_rows * num_of_cols) = O(num_of_rows^2 * num_of_cols^2).