Word Search

Problem: Word Search

Since we only need to check whether one single word exists in the board, we can use backtracking to solve this problem. We first find possible start for word in the whole board, then check its neighbor whether fit the second character of the word, thus repeating recursively. If we checked all character of the word, we can return True. If there's no up to standard neighbor, we try other possible way.

Code in Python:

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        visited = []
        def cExist(pos):
            if pos == len(word):
                return True
            if pos:
                i, j = visited[-1][0], visited[-1][1]
                if i < len(board)-1:
                    if board[i+1][j] == word[pos] and [i+1,j] not in visited:
                        visited.append([i+1,j])
                        if cExist(pos+1): return True
                        visited.pop()
                if i > 0:
                    if board[i-1][j] == word[pos] and [i-1,j] not in visited:
                        visited.append([i-1,j])
                        if cExist(pos+1): return True
                        visited.pop()
                if j < len(board[0])-1:
                    if board[i][j+1] == word[pos] and [i, j+1] not in visited:
                        visited.append([i,j+1])
                        if cExist(pos+1): return True
                        visited.pop()
                if j > 0:
                    if board[i][j-1] == word[pos] and [i,j-1] not in visited:
                        visited.append([i,j-1])
                        if cExist(pos+1): return True
                        visited.pop()
            else:
                for i in xrange(len(board)):
                    for j in xrange(len(board[0])):
                        if board[i][j] == word[pos] and [i,j] not in visited:
                            visited.append([i,j])
                            if cExist(pos+1):
                                return True
                            visited.pop()
                return False
        return cExist(0)