leetcood学习笔记-79-单词搜索

佚名 6年前 (2019-04-22) 随笔 1016人围观抢沙发百度已收录

题目描述：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

方法一;回溯

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        max_x,max_y,max_step = len(board)-1,len(board[0])-1,len(word)-1
        def maze(x, y,step,visited):
            if visited[x][y]==1:
                return False
            if board[x][y] != word[step]:
                return False
            if step==max_step:
                return True
            visited[x][y]=1
            if x < max_x and maze(x+1,y,step+1,visited):
                return True
            if x>0 and maze(x-1,y,step+1,visited):
                return True
            if y<max_y and maze(x,y+1,step+1,visited):
                return True
            if y>0 and maze(x,y-1,step+1,visited):
                return True
            # 记得失败后要置零
            visited[x][y]=0
            return False
        visited = [[0]*(max_y+1) for i in range(max_x+1)]
        for x in range(max_x+1):
            for y in range(max_y+1):
                if board[x][y] != word[0]:
                    continue
                if maze(x,y,0,visited):
                    return True
        return False

优化：

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        max_x,max_y,max_step = len(board)-1,len(board[0])-1,len(word)-1
        def maze(x, y,step,visited):
            if visited[x][y]==1:
                return False
            if board[x][y] != word[step]:
                return False
            if step==max_step:
                return True
            visited[x][y]=1
            if x < max_x and maze(x+1,y,step+1,visited):
                return True
            if x>0 and maze(x-1,y,step+1,visited):
                return True
            if y<max_y and maze(x,y+1,step+1,visited):
                return True
            if y>0 and maze(x,y-1,step+1,visited):
                return True
            # 记得失败后要置零
            visited[x][y]=0
            return False
        visited = [[0]*(max_y+1) for i in range(max_x+1)]
        need={}
        for c in word:
            if c in need:
                need[c]+=1  
            else:
                need[c]=1
        for i in range(max_x+1):
            for j in range(max_y+1):
                if board[i][j] in need:
                    need[board[i][j]] -=1
        for c in need:
            if need[c] >0:
                return False
        for x in range(max_x+1):
            for y in range(max_y+1):
                if board[x][y] != word[0]:
                    continue
                if maze(x,y,0,visited):
                    return True
        return False