Word Search

此题其实也是一个回溯题，从DFS的函数写法上就能看出来，不过这里是四方向DFS，其实也就是O(4 ^ n)的时间复杂度，另外这里需要注意哈希表查重的问题，即每次循环完了之后需要把当前点从查重集合中删去，因为我们有可能从另外一个起点DFS再到达这个地方

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

        m = len(board[0])
        if not m:
            return False

        checker = set([])
        for i in xrange(n):
            for j in xrange(m):
                if board[i][j] == word[0]:
                    if self.DFS(board, n, m, checker, 0, word, i, j):
                        return True

        return False

    def DFS(self, board, n, m, checker, base, word, row, col):
        if base == len(word) - 1:
            return True

        checker.add((row, col))
        for i, j in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
            curRow, curCol = row + i, col + j
            if 0 <= curRow < n and 0 <= curCol < m and (curRow, curCol) not in checker:
                if board[curRow][curCol] == word[base + 1]:
                    if self.DFS(board, n, m, checker, base + 1, word, curRow, curCol):
                        return True

        checker.remove((row, col))
        return False

搜索问题如果没有特殊的条件，想要O(1)空间复杂度，就只能借助改变原矩阵的值来查重了

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

        m = len(board[0])
        if not m:
            return False

        for i in xrange(n):
            for j in xrange(m):
                if board[i][j] == word[0]:
                    if self.DFS(board, i, j, n, m, word, 0, len(word)):
                        return True

        return False

    def DFS(self, board, row, col, n, m, string, start, end):
        if start >= end - 1:
            return True

        tmp = '1'
        tmp, board[row][col] = board[row][col], tmp
        for i, j in ((0, 1), (1, 0), (-1, 0), (0, -1)):
            curRow, curCol = row + i, col + j
            if 0 <= curRow < n and 0 <= curCol < m:
                if board[curRow][curCol] != '1' and string[start + 1] == board[curRow][curCol]:
                    if self.DFS(board, curRow, curCol, n, m, string, start + 1, end):
                        return True

        tmp, board[row][col] = board[row][col], tmp
        return False