[数据结构与算法]leetcode 79. 单词搜索 python

题目描述：

?

?

?题解：回溯

参考LeetCode 79 Word Search (Python) - 小明MaxMing

1.定义函数dfs，输入为一个坐标(posx,posy)，需要匹配的字符串s和当前已经匹配到的下标idx，如果idx=len(s)说明已经完成了匹配，返回true，如果(posx,posy)超出界限或者与下一个需要匹配的s中的字符不同则返回，否则对当前位置的上下左右四个相邻位置调用dfs。

2.对输入board的每个位置进行搜索，如果找到一个位置与s第一个字符相等则调用dfs。

需要注意的地方：

1.在对相邻的四个位置调用dfs的时候，可能会对之前搜索过的位置进行重复搜索，所以定义一个visited数组，全部初始化为0，搜索过的对应位置值设置为1.

2.用idx记录当前匹配到的位置，不修改需要匹配的字符串。

3.在对(posx,posy)调用dfs前将该位置visited设为1，调用结束后重新修改为0，对应回溯的过程。

4.对输入board每个位置(i,j)进行判断，如果board[i][j]=word[0]，则对该位置调用dfs，注意此时idx从1开始而不是从0，因为进入dfs就说明第一个字符已经匹配成功了。

class Solution(object):
    def exist(self, board, word):
        m = len(board)
        n = len(board[0])
        visited = [[0 for j in range(n)]for i in range(m)]
        directions = [(-1,0),(1,0),(0,-1),(0,1)]
        def dfs(posx,posy,idx):
            if idx==len(word):
                return True
            for dx,dy in directions:
                newx = posx+dx
                newy = posy+dy
                if 0<=newx<m and 0<=newy<n and visited[newx][newy]==0 and board[newx][newy]==word[idx]:
                    visited[newx][newy]=1
                    if dfs(newx,newy,idx+1):
                        return True
                    visited[newx][newy]=0
            return False
        for i in range(m):
            for j in range(n):
                if board[i][j]==word[0]:
                    visited[i][j]=1
                    if dfs(i,j,1):
                        return True
                    visited[i][j]=0
        return False

?

?