L79. Word Search

79. Word Search

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

        r = len(board)
        c = len(board[0])
        for i in range(r):
            for j in range(c):
                if self.helper(board, word, i, j, 0):
                    return True
        return False


    def helper(self, board, word, row, col, k):
        dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        if row > len(board) - 1 or row < 0 or col > len(board[0])-1 or col < 0:
            return False
        if board[row][col] != word[k]:
            return False
        else:
            if k == len(word) - 1:
                return True
            else:
                temp = False
                for dir in dirs:
                    val = board[row][col]
                    board[row][col] = None
                    temp = temp or self.helper(board, word, row + dir[0], col + dir[1], k + 1) # 有一个方向match上即可
                    board[row][col] = val
                return temp

class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """

        m = len(board)
        n = len(board[0])

        for i in range(m):
            for j in range(n):
                if self.dfs(board, word,i, j, 0):
                    return True 
        return False



    def dfs(self,table, word, i, j, k):
        m = len(table) 
        n = len(table[0])

        if k > len(word) - 1:
            return False

        if i>= 0 and i < m and j>=0 and j < n and table[i][j] == word[k]:
            if k == len(word) - 1:
                return True
            val = table[i][j]
            table[i][j] = None
            temp = (self.dfs(table, word,i+1, j, k + 1) or self.dfs(table, word,i-1,j, k + 1) or \
                    self.dfs(table, word,i, j+1, k + 1) or self.dfs(table, word,i, j-1, k + 1))

            table[i][j] = val
            return temp

#self.table


class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """

        m = len(board)
        n = len(board[0])

        self.table = board
        for i in range(m):
            for j in range(n):
                if self.dfs( word,i, j, 0):
                    return True 
        return False



    def dfs(self, word, i, j, k):
        m = len(self.table) 
        n = len(self.table[0])

        if k > len(word) - 1:
            return False

        if i>= 0 and i < m and j>=0 and j < n and self.table[i][j] == word[k]:
            if k == len(word) - 1:
                return True
            val = self.table[i][j]
            self.table[i][j] = None
            temp = (self.dfs( word,i+1, j, k + 1) or self.dfs( word,i-1,j, k + 1) or \
                    self.dfs( word,i, j+1, k + 1) or self.dfs( word,i, j-1, k + 1))

            self.table[i][j] = val
            return temp

212. Word Search II

Directly using word search I will cause Time Limit Exceeded

class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        result = []
        for word in words:
            if self.exist(board, word) and word not in result:
                result.append(word)

        return result



    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """

        m = len(board)
        n = len(board[0])

        self.table = board
        for i in range(m):
            for j in range(n):
                if self.dfs( word,i, j, 0):
                    return True 
        return False


    def dfs(self, word, i, j, k):
        m = len(self.table) 
        n = len(self.table[0])

        if k > len(word) - 1:
            return False

        if i>= 0 and i < m and j>=0 and j < n and self.table[i][j] == word[k]:
            if k == len(word) - 1:
                return True
            val = self.table[i][j]
            self.table[i][j] = None
            temp = (self.dfs( word,i+1, j, k + 1) or self.dfs( word,i-1,j, k + 1) or \
                    self.dfs( word,i, j+1, k + 1) or self.dfs( word,i, j-1, k + 1))

            self.table[i][j] = val
            return temp