[数据结构与算法] 【题解】Leetcode周赛292 检查是否有合法括号字符串路径 JAVA

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【题解】Leetcode周赛292 检查是否有合法括号字符串路径 JAVA -> 正文阅读

[数据结构与算法]【题解】Leetcode周赛292 检查是否有合法括号字符串路径 JAVA

检查是否有合法括号字符串路径

题目来源：Leetcode周赛292

标签：动态规划、DFS

一个括号字符串是一个非空且只包含 '(' 和 ')' 的字符串。如果下面任意条件为真，那么这个括号字符串就是 合法的 。

字符串是 () 。
字符串可以表示为 AB（A 连接 B），A 和 B 都是合法括号序列。
字符串可以表示为 (A) ，其中 A 是合法括号序列。

给你一个 m x n 的括号网格图矩阵 grid 。网格图中一个 合法括号路径 是满足以下所有条件的一条路径：

路径开始于左上角格子 (0, 0) 。
路径结束于右下角格子 (m - 1, n - 1) 。
路径每次只会向下或者向右移动。
路径经过的格子组成的括号字符串是合法的。

如果网格图中存在一条 合法括号路径 ，请返回 true ，否则返回 false 。

示例 1：

在这里插入图片描述

输入：grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
输出：true
解释：上图展示了两条路径，它们都是合法括号字符串路径。
第一条路径得到的合法字符串是 "()(())" 。
第二条路径得到的合法字符串是 "((()))" 。
注意可能有其他的合法括号字符串路径。

示例 2：

在这里插入图片描述

输入：grid = [[")",")"],["(","("]]
输出：false
解释：两条可行路径分别得到 "))(" 和 ")((" 。由于它们都不是合法括号字符串，我们返回 false 。

开始写的搜索版本，超时了hhhh(写的时候就猜到了)

class Solution {
    int [][] dirs = new int[][]{{1,0},{0,1}};
    int n,m;
    StringBuilder sb;
    private boolean dfs(int x,int y,char[][] grid){
        if (x == n-1 && y == m-1){
            Deque<Character> st = new ArrayDeque<>();
            String s = sb.toString();
            for (int i = 0;i < s.length();i++){
                char c = s.charAt(i);
                if (c == '('){
                    st.offerLast(c);
                }else{
                    if (st.isEmpty()) return false;
                    if (st.peekLast() == ')') return false;
                    else st.pollLast();
                }
            }
            if (st.isEmpty()) return true;
            else return false;
        }
        for (int i = 0;i < 2;i++){
            int nx = x + dirs[i][0];
            int ny = y + dirs[i][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            sb.append(grid[nx][ny]);
            if (dfs(nx,ny,grid)) return true;
            sb.deleteCharAt(sb.length()-1);
        }
        return false;
    }
    public boolean hasValidPath(char[][] grid) {
        n = grid.length;
        m = grid[0].length;
        sb = new StringBuilder();
        sb.append(grid[0][0]);
        return dfs(0,0,grid);
    }
}

然后进行了优化+剪枝

优化1：用一个变量 cc 表示括号字符串的平衡度：遇到 $^{'} (^{'}$ 就 +1，遇到 $^{'})^{'}$ 就 ?1。那么合法字符串等价于任意时刻 $c\ge 0 且最后 c=0$ 。
- 剪枝：当某个时刻 $c < 0 或者 c > (n + m ? 1) / 2$ 时，直接剪枝返回false。
  
  c > (n+m-1) / 2 表示就算后面全是 ) 也不满足条件
优化2：把进入格子前的 cc 值当作格子的附加状态，那么一个格子至多有 $(m + n ? 1) / 2$ 种不同的状态，整个网格图至多有 $m n (m + n ? 1) / 2$ 个不同的状态。

class Solution {
    int [][] dirs = new int[][]{{1,0},{0,1}};
    int n,m;
    boolean [][][] used;
    private boolean dfs(int x,int y,char[][] grid,int c){
        if (x == n-1 && y == m-1){
            return c == 0;
        }
        if (c > (n+m-1)/2) return false;
        for (int i = 0;i < 2;i++){
            int nx = x + dirs[i][0];
            int ny = y + dirs[i][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            int ct = c + (grid[nx][ny] == '(' ? 1 : -1);
            if (ct < 0 || used[nx][ny][ct]) continue;
            used[nx][ny][ct] = true;
            if (dfs(nx,ny,grid,ct)) return true;
        }
        return false;
    }
    public boolean hasValidPath(char[][] grid) {
        n = grid.length;
        m = grid[0].length;
        if ((n+m) % 2 == 0 || grid[0][0] == ')' || grid[n-1][m-1] == '(') return false;
        used = new boolean[n][m][n+m];
        int c = (grid[0][0] == '(' ? 1 : -1);
        used[0][0][c] = true;
        return dfs(0,0,grid,c);
    }
}

动态规划：
在这里插入图片描述

记 f(i, j, k) 表示是否存在以格子 (i,j) 为结尾，且 now 值是 k 的括号序列。由于只能往右或往下走，我们有如下转移：

$\leftarrow \begin{cases} f(i - 1, j, k - c) & \text{if } i > 0 \text{（从上面转移过来）} \\ f(i, j - 1, k - c) & \text{if } j > 0 \text{（从左边转移过来）} \end{cases}$
其中若 $g r i d [i] [j] = =^{'} (^{'}$ ,则 $c = 1$ 否则 $c = ? 1$ 。k 的范围是 $[0, n + m)$ （因为过程中 now 不能为负数，且最长路径只有 $n + m ? 1$ 这么长），初始值即为 $\text{true}$ （因为 $g r i d [0] [0]$ 必须是左括号，否则不合法）。复杂度 $\mathcal{O}(nm(n + m))$ 。

class Solution {
    public boolean hasValidPath(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        if ((n+m) % 2 == 0 || grid[0][0] == ')' || grid[n-1][m-1] == '(') return false;
        boolean [][][] dp = new boolean[n][m][n+m];
        dp[0][0][1] = true;
        for (int i = 0;i < n;i++){
            for (int j = 0;j < m;j++){
                int c = grid[i][j] == '(' ? 1 : -1;
                for (int k = 0;k < n+m;k++){
                    int t =  k - c;
                    if (t  < 0 || t >= n+m) continue;
                    if (i > 0) dp[i][j][k] = dp[i][j][k] || dp[i-1][j][t];
                    if (j > 0) dp[i][j][k] = dp[i][j][k] || dp[i][j-1][t];
                }
            }
        }
        return dp[n-1][m-1][0];
    }
}