[数据结构与算法]leetcode：6059. 检查是否有合法括号字符串路径【又是一道直接气晕的题 + dfs + 记忆化搜索 + 括号套路】

分析

总路径长度是m + n - 1必须为偶数
然后从00触发，dfs记录x，y，cntLeft， cntRight
如果xy到达终点并且cntLeft == cntRight就成功哦
如果中途出现cntRight > cntLeft就凉凉return
dfs遍历下或者右，如果在合法范围内，就加上当前grid[x][y]的左右括号值
核心：保证左括号 >= 右括号数 ，且最终相等

记忆化搜索
我就是漏了
import functools
@functools.lru_cache(None)
这个dfs配套的记忆化搜索装饰器就wa了
气晕气晕气晕

ac code

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        print(m, n)
        if (m + n - 1) % 2 != 0:
            return False
        

        
        #visit = [[False] * n for _ in range(m)]
        #visit[0][0] = True
        flag = False
        
        import functools
        @functools.lru_cache(None)
        def bfs(x, y, cntLeft, cntRight):
            nonlocal flag
            #print(x, y, cntLeft, cntRight)
            if x == m - 1 and y == n - 1 and cntLeft == cntRight:
                flag = True
                return
            if flag is True:
                return
            
            if cntRight > cntLeft:
                return
            
            #if cntLeft > (m + n - 1) // 2:
                #return
            
            for x1, y1 in [(1, 0), (0, 1)]:
                new_x = x + x1
                new_y = y + y1
                if 0 <= new_x < m and 0 <= new_y < n:
                    #visit[new_x][new_y] = True
                    if grid[new_x][new_y] == '(':
                        bfs(new_x, new_y, cntLeft + 1, cntRight)
                    else:
                        bfs(new_x, new_y, cntLeft, cntRight + 1)
                    #visit[new_x][new_y] = False
        
        if grid[0][0] == '(':
            bfs(0, 0, 1, 0)
        else:
            bfs(0, 0, 0, 1)
        if flag:
            return True
        else:
            return False

总结

括号的套路（左括号 <= 右括号恒成立，且最终左右括号相等）
dfs的套路（通过@functools.lru_cache(None))装饰器优化
我离第三次ak就差一两行
直接气晕

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖