Leetcode: Word Search

Word Search

Similar Problems:

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 =

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/word-search
## Basic Ideas: backtracking
## Complexity: Time ?, Space ?
class Solution(object):
    def exist(self, board, word):
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        word_len = len(word)
        if word_len == 0: return True

        self.row_count = len(board)
        if self.row_count == 0: return False
        self.col_count = len(board[0])

        l = []
        for i in xrange(self.row_count):
            for j in xrange(self.col_count):
                if board[i][j] == word[0]:
                    if word_len == 1: return True
                    l.append((i, j))
                    if self.myExist(board, i, j, l, word[1:]):
                        return True
        return False

    def myExist(self, board, i, j, l, word):
        if len(word) == 0: return True
        # check the neighbors of board[i][j]
        for (ik, jk) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            i2, j2 = i+ik, j+jk
            if i2<0 or i2>=self.row_count or j2<0 or j2>=self.col_count:
            if board[i2][j2] != word[0] or (i2, j2) in l:
            # go deeper with this direction
            l.append((i2, j2))
            if self.myExist(board, i2, j2, l, word[1:]):
                return True
                # restore context
        return False

# s = Solution()
# print s.exist([["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]], "ABCESEEEFS") # True
# print s.exist([["C","A","A"],["A","A","A"],["B","C","D"]], "AAB") # true

Share It, If You Like It.

Leave a Reply

Your email address will not be published.