讨论/《深度优先搜索》 - 例题:单词搜索/
《深度优先搜索》 - 例题:单词搜索
共 1 个回复
class Solution:
    def exist(self, mtx: List[List[str]], s: str) -> bool:
        dic = collections.defaultdict(int)
        for i in range(len(mtx)):
            for j in range(len(mtx[0])):
                dic[mtx[i][j]] += 1
        for x in s: # 针对数量的预处理
            dic[x] -= 1
            if dic[x] < 0:
                return False
        drt = [[-1,0],[1,0],[0,1],[0,-1]]
        def dfs(ss,x,y):
            if not ss:
                return True
            for d in drt:
                xx = x + d[0]
                yy = y + d[1] 
                if 0<= xx < len(mtx) and 0<= yy < len(mtx[0]) \
                    and mtx[xx][yy] == ss[0]:
                    mtx[xx][yy] = '-'
                    if dfs(ss[1:],xx,yy):
                        return True
                    mtx[xx][yy] = ss[0]
            return False
        for i in range(len(mtx)):
            for j in range(len(mtx[0])):
                if mtx[i][j] == s[0]:
                    mtx[i][j] = '-'
                    if dfs(s[1:],i,j): 
                        return True
                    mtx[i][j] = s[0]
        return False