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

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

好难好难，这又是一个合法括号问题！！只不过更加的难，太难了，太难了，自闭！！！

关于括号相关问题的分析，可见：「秒杀所有括号类问题」「回溯算法：括号生成」「回溯算法：删除无效的括号」

总结分析了这么多，其实关于括号类问题大部分都是使用「DFS」，关于 DFS 详细分析可见 回溯 (DFS) 算法框架

但是难点就在于「剪枝」，太变态了！！！回溯算法：删除无效的括号 里面详细介绍了一些剪枝的策略！！

暴力 DFS

下面来看今天的问题！第一眼感觉不难，随手就写了一个「DFS」，不就是找到一条从(0, 0)到(m - 1, n - 1)的满足要求的路径嘛！！和题目 最小路径和 中「暴力 DFS 求解」很类似，可见 浅析：最小路径和

所以随手就写出了代码：

x
private boolean ok = false;
public boolean hasValidPath(char[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    dfs(grid, 0, 0, 0, 0, new boolean[m][n]);
    return ok;
}
private void dfs(char[][] grid, int i, int j, int left, int right, boolean[][] used) {
    int m = grid.length;
    int n = grid[0].length;
    if (i < 0 || i >= m || j < 0 || j >= n || used[i][j] || left < right || ok) return ;
    used[i][j] = true;
    if (grid[i][j] == '(') left++;
    else right++;
    if (i == m - 1 && j == n - 1) {
        if (left == right) ok = true;
    }
    dfs(grid, i + 1, j, left, right, used);
    dfs(grid, i, j + 1, left, right, used);
    used[i][j] = false;
}

无奈，超时了！！！

剪枝思路分析

如何优化呢？？？剪枝吧！！

角度一：由于只能往下或者往右，且起点为(0, 0)，终点为(m - 1, n -1)，所以任意一条路径长度均为m + n - 1。如果要满足「合法括号」的要求，m + n - 1 必为偶数

角度二：起点(0, 0)必须为'('，而终点(m - 1, n - 1)必须为')'，才能满足要求

角度三：在「暴力 DFS」中，我们对状态划分比较简单，仅划分为了m * n个，即以每个格子为单位，用used[][]表示

我们现在优化一下代码，不再用left和right表示左右括号的数量，而是只用一个变量count表示，即：遇到左括号就 +1，遇到右括号就 -1。如果count < 0，则非法需要被剪枝

我们现在分析一下count的范围，如果所有的括号均为左括号，那么count为最大值，即：count = m * n - 1。因为上面分析过了，任意一条路径长度均为m + n - 1

所以如果我们仅仅以每个格子为状态，我们在回溯的过程中需要撤销标记，可能会导致冗余的计算。如果我们以每个格子的count作为状态，那么这个used[m][n][m + n]同时还充当了「备忘录 emeo」的角色

优化后代码实现

x
public boolean hasValidPath(char[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    // 角度一 + 角度二 的剪枝
    if ((m + n) % 2 == 0 || grid[0][0] == ')' || grid[m - 1][n - 1] == '(') return false;
    return dfs(grid, 0, 0, 0, new boolean[m][n][m + n]);
}
private boolean dfs(char[][] grid, int i, int j, int count, boolean[][][] used) {
    int m = grid.length;
    int n = grid[0].length;
    // 边界处理
    if (i < 0 || i >= m || j < 0 || j >= n) return false;
    // count < 0 说明 left < right
    // count > m - i + n - j - 1 说明剩下的路径就算都是 ')' 也无法使 count 变为 0
    if (count < 0 || count > m - i + n - j - 1) return false;
    // 该状态已标记，无法满足合法括号路径
    if (used[i][j][count]) return false;
    // 到达终点，count = 1 即满足要求
    // 可以思考一下为什么 count = 1 就行了
    if (i == m - 1 && j == n - 1) return count == 1;
    used[i][j][count] = true;
    count += (grid[i][j] == '(' ? 1 : -1);
    // 处理下方和右方
    return  dfs(grid, i + 1, j, count, used) || dfs(grid, i, j + 1, count, used);
}