word search

不幸的回溯法超时了，经过改进的办法：

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])
        visit = [[0 for i in range(n)] for j in range(m)]
        flag = False
        for i in range(m):
            for j in range(n):
                if self.check(board,word,i,j,0,m,n,visit):
                    return True
        return False
    def check(self,board,word,r,c,w,m,n,visit):
        if w == len(word):
            return True
        if board[r][c] == word[w] and visit[r][c] == 0:
            visit[r][c] = 1
            if w == len(word) - 1:
                return True
            if r - 1 >= 0:
                if self.check(board,word,r-1,c,w+1,m,n,visit):
                    return True
            if r + 1 < m:
                if self.check(board,word,r+1,c,w+1,m,n,visit):
                    return True
            if c - 1 >= 0:
                if self.check(board,word,r,c-1,w+1,m,n,visit):
                    return True
            if c + 1 < n:
                if self.check(board,word,r,c+1,w+1,m,n,visit):
                    return True
            visit[r][c] = 0
        return False

省了空间的做法：

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])
        #visit = [[0 for i in range(n)] for j in range(m)]
        flag = False
        for i in range(m):
            for j in range(n):
                if self.check(board,word,i,j,0,m,n):
                    return True
        return False
    def check(self,board,word,r,c,w,m,n):
        if w == len(word):
            return True
        if board[r][c] == word[w]:
        #and visit[r][c] == 0:
            t = board[r][c]
            board[r][c] = ''
            if w == len(word) - 1:
                return True
            if r - 1 >= 0:
                if self.check(board,word,r-1,c,w+1,m,n):
                    return True
            if r + 1 < m:
                if self.check(board,word,r+1,c,w+1,m,n):
                    return True
            if c - 1 >= 0:
                if self.check(board,word,r,c-1,w+1,m,n):
                    return True
            if c + 1 < n:
                if self.check(board,word,r,c+1,w+1,m,n):
                    return True
            board[r][c] = t
        return False

再加上四方向的合并，空间节省：

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])
        #visit = [[0 for i in range(n)] for j in range(m)]
        flag = False
        for i in range(m):
            for j in range(n):
                if self.check(board,word,i,j,0,m,n):
                    return True
        return False
    def check(self,board,word,r,c,w,m,n):
        if r < 0 or c < 0 or r >= m or c >= n:
            return False
        if w == len(word):
            return True
        if board[r][c] == word[w]:
        #and visit[r][c] == 0:
            t = board[r][c]
            board[r][c] = ''
            if w == len(word) - 1:
                return True
            if self.check(board,word,r-1,c,w+1,m,n):
                return True    
            if self.check(board,word,r+1,c,w+1,m,n):
                return True
            if self.check(board,word,r,c-1,w+1,m,n):
                return True
            if self.check(board,word,r,c+1,w+1,m,n):
                return True
            board[r][c] = t
        return False

合并到一起

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])
        #visit = [[0 for i in range(n)] for j in range(m)]
        flag = False
        for i in range(m):
            for j in range(n):
                if self.check(board,word,i,j,0,m,n):
                    return True
        return False
    def check(self,board,word,r,c,w,m,n):
        if r < 0 or c < 0 or r >= m or c >= n:
            return False
        if w == len(word):
            return True
        if board[r][c] == word[w]:
        #and visit[r][c] == 0:
            t = board[r][c]
            board[r][c] = ''
            if w == len(word) - 1:
                return True
            if self.check(board,word,r-1,c,w+1,m,n) or self.check(board,word,r+1,c,w+1,m,n) or self.check(board,word,r,c-1,w+1,m,n) or self.check(board,word,r,c+1,w+1,m,n):
                return True 
            board[r][c] = t
        return False