Hard

题目描述

括号字符串是仅由 ‘(’ 和 ‘)’ 组成的非空字符串。如果满足以下任一条件，则该字符串是有效的：

  • 它是 ()
  • 它可以写成 AB（A 与 B 连接），其中 A 和 B 都是有效的括号字符串
  • 它可以写成 (A)，其中 A 是有效的括号字符串

给定一个 m x n 的括号网格矩阵。网格中的有效括号字符串路径是满足以下所有条件的路径：

  • 路径从左上角单元格 (0, 0) 开始
  • 路径在右下角单元格 (m - 1, n - 1) 结束
  • 路径只能向下或向右移动
  • 路径形成的括号字符串是有效的

如果网格中存在有效的括号字符串路径，返回 true，否则返回 false。

示例 1：

输入：grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
输出：true
解释：上图显示了两条形成有效括号字符串的可能路径。
第一条路径形成有效括号字符串 "()(())"。
第二条路径形成有效括号字符串 "((()))"。
注意可能存在其他有效的括号字符串路径。

示例 2：

输入：grid = [[")",")"],["(","("]]
输出：false
解释：两条可能的路径形成括号字符串 "))(" 和 ")(("。由于它们都不是有效的括号字符串，我们返回 false。

约束条件：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • grid[i][j] 是 ‘(’ 或 ‘)’

解题思路

这是一道动态规划题目。关键观察是：对于任何有效的括号字符串的前缀，左括号的数量必须大于或等于右括号的数量。

我们可以用三维DP来解决：dp[i][j][k] 表示到达位置 (i,j) 时，当前路径的左括号减去右括号的差值为 k 是否可能。

状态定义：

  • dp[i][j][k] = true 表示可以到达位置 (i,j) 且括号平衡值为 k
  • 括号平衡值：遇到 ‘(’ 时 +1，遇到 ‘)’ 时 -1

状态转移：

  • 从上方转移：dp[i][j][k] |= dp[i-1][j][prev_k]
  • 从左方转移：dp[i][j][k] |= dp[i][j-1][prev_k]
  • 其中 prev_k 根据当前字符调整：
    • 如果 grid[i][j] == '('，则 prev_k = k - 1
    • 如果 grid[i][j] == ')'，则 prev_k = k + 1

边界条件：

  • 起点 dp[0][0][1] = true（如果 grid[0][0] == '('）
  • 平衡值不能为负数（保证括号序列的有效性前缀条件）

优化： 可以使用滚动数组或者用集合记录每个位置可能的平衡值，减少空间复杂度。

代码实现

class Solution {
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int maxLen = m + n - 1;
        
        // dp[i][j] 存储在位置(i,j)可能的平衡值集合
        vector<vector<set<int>>> dp(m, vector<set<int>>(n));
        
        // 初始化起点
        if (grid[0][0] == '(') {
            dp[0][0].insert(1);
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                
                char ch = grid[i][j];
                int delta = (ch == '(') ? 1 : -1;
                
                // 从上方转移
                if (i > 0) {
                    for (int prev : dp[i-1][j]) {
                        int curr = prev + delta;
                        if (curr >= 0 && curr <= maxLen) {
                            dp[i][j].insert(curr);
                        }
                    }
                }
                
                // 从左方转移
                if (j > 0) {
                    for (int prev : dp[i][j-1]) {
                        int curr = prev + delta;
                        if (curr >= 0 && curr <= maxLen) {
                            dp[i][j].insert(curr);
                        }
                    }
                }
            }
        }
        
        return dp[m-1][n-1].count(0) > 0;
    }
};

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        max_len = m + n - 1
        
        # dp[i][j] 存储在位置(i,j)可能的平衡值集合
        dp = [[set() for _ in range(n)] for _ in range(m)]
        
        # 初始化起点
        if grid[0][0] == '(':
            dp[0][0].add(1)
        
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                
                ch = grid[i][j]
                delta = 1 if ch == '(' else -1
                
                # 从上方转移
                if i > 0:
                    for prev in dp[i-1][j]:
                        curr = prev + delta
                        if 0 <= curr <= max_len:
                            dp[i][j].add(curr)
                
                # 从左方转移
                if j > 0:
                    for prev in dp[i][j-1]:
                        curr = prev + delta
                        if 0 <= curr <= max_len:
                            dp[i][j].add(curr)
        
        return 0 in dp[m-1][n-1]

public class Solution {
    public bool HasValidPath(char[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int maxLen = m + n - 1;
        
        // dp[i][j] 存储在位置(i,j)可能的平衡值集合
        HashSet<int>[,] dp = new HashSet<int>[m, n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = new HashSet<int>();
            }
        }
        
        // 初始化起点
        if (grid[0][0] == '(') {
            dp[0, 0].Add(1);
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                
                char ch = grid[i][j];
                int delta = ch == '(' ? 1 : -1;
                
                // 从上方转移
                if (i > 0) {
                    foreach (int prev in dp[i-1, j]) {
                        int curr = prev + delta;
                        if (curr >= 0 && curr <= maxLen) {
                            dp[i, j].Add(curr);
                        }
                    }
                }
                
                // 从左方转移
                if (j > 0) {
                    foreach (int prev in dp[i, j-1]) {
                        int curr = prev + delta;
                        if (curr >= 0 && curr <= maxLen) {
                            dp[i, j].Add(curr);
                        }
                    }
                }
            }
        }
        
        return dp[m-1, n-1].Contains(0);
    }
}

var hasValidPath = function(grid) {
    const m = grid.length, n = grid[0].length;
    const maxLen = m + n - 1;
    
    // dp[i][j] 存储在位置(i,j)可能的平衡值集合
    const dp = Array(m).fill(null).map(() => 
        Array(n).fill(null).map(() => new Set())
    );
    
    // 初始化起点
    if (grid[0][0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(m × n × (m + n))
空间复杂度O(m × n × (m + n))

说明：

  • 时间复杂度：对于每个位置 (i,j)，最多有 O(m+n) 种可能的平衡值，需要遍历所有可能的状态进行转移
  • 空间复杂度：需要存储每个位置所有可能的平衡值，最坏情况下每个位置有 O(m+n) 种状态

相关题目