LeetCode 解題筆記：2267. Check if There Is a Valid Parentheses String Path

作者：王一哲
日期：2026年9月29日


LeetCode 題目連結：2267. Check if There Is a Valid Parentheses String Path

解題想法

困難題。題目給一只有 $($ 及 $)$ 的二維陣列 $grid$，假設陣列的大小為 $m \times n$，判斷這個陣列是否可以找到符合以下的條件路徑：

1. 括號成對
2. 從左上角 $(0, 0)$ 出發，走到右下角 $(m-1, n-1)$。
3. 只能往下走或往右走

有 3 種狀況括號一定不成對，可以直接回傳 False：

1. 總步數 $m + n - 1$ 如果是奇數
2. $grid[0][0] == ')'$
3. $grid[m-1][n-1] == '('$

題目下方提示這題要用動態規畫解題，用記憶化的 DFS 比較方便。用一個變數 $balance$ 計算左括號比右括號多幾個，如果路徑上的括號成對，則路徑上任何一格的 $balance \geq 0$，路徑上最後一格 $balance == 0$。先用一個 Python dict 或 C++ map 記錄已經算過的狀況，key 為坐標及括號數量差 $(r, c, balance)$，value 為 True 或 False。如果用 Python 解題，也可以用 functools.cache，在自訂函式 $dfs$ 前一行加上裝飾器 $@cache$。寫一個自訂函式 $dfs$，代入 $r, c, balance$，函式主要分成以下7個部分：

1. 更新左括號減右括號數量
2. 如果 memo 之中有已經算過的結果，直接回傳
3. 剪枝，如果右括號比左括號多，不符合規則，回傳 False。
4. 遞迴出口，抵達終點，檢查左、右括號是否一樣多。
5. 遞迴，向下走。如果向下走可以找到合法的路徑，記錄 $(r, c, balance)$ 的狀態為 True，回傳 True。
6. 遞迴，向右走。如果向右走可以找到合法的路徑，記錄 $(r, c, balance)$ 的狀態為 True，回傳 True。
7. 如果前兩個遞迴沒有找到合法的路徑，記錄 $(r, c, balance)$ 的狀態為 False，回傳 False。

Python 程式碼

使用 map 記錄狀態。Runtime: 7 ms, beats 96.00%. Memory: 29.92 MB, beats 72.00%.

class Solution:
    def hasValidPath(self, grid: list[list[str]]) -> bool:
        m, n = len(grid), len(grid[0])  # m 列、n 欄
        
        # 特例，如果總步數 m + n - 1 是奇數，不可能平衡
        if (m + n - 1) % 2 == 1: return False
        
        # 特例，grid[0][0] 是 )，不可能平衡
        if grid[0][0] == ')': return False
        
        # 特例，grid[m-1][n-1] 是 (，不可能平衡
        if grid[m-1][n-1] == '()': return False

        # 記憶化 dfs，不使用 functools.cache
        # 代入坐標 (r, c)，左括號減右括號數量 balance
        memo = dict()  # (r, c, balance): True or False
        
        def dfs(r, c, balance):
            # 更新左括號減右括號數量
            if grid[r][c] == '(':
                balance += 1
            else:
                balance -= 1
            
            # 如果 memo 之中有已經算過的結果，直接回傳
            if (r, c, balance) in memo:
                return memo[r, c, balance]

            # 剪枝，如果右括號比左括號多，不符合規則，回傳 False
            if balance < 0: return False

            # 遞迴出口，抵達終點，檢查左、右括號是否一樣多
            if r == m-1 and c == n-1:
                return balance == 0
            
            # 遞迴，向下走
            if r < m-1 and dfs(r+1, c, balance):
                memo[r, c, balance] = True
                return True
            
            # 遞迴，向右走
            if c < n-1 and dfs(r, c+1, balance):
                memo[r, c, balance] = True
                return True
            
            # 預設回傳 False
            memo[r, c, balance] = False
            return False
        
        # 呼叫 dfs 求答案
        return dfs(0, 0, 0)

使用 functools.cache。Runtime: 7 ms, beats 96.00%. Memory: 30.04 MB, beats 71.00%.

from functools import cache

class Solution:
    def hasValidPath(self, grid: list[list[str]]) -> bool:
        m, n = len(grid), len(grid[0])  # m 列、n 欄
        
        # 特例，如果總步數 m + n - 1 是奇數，不可能平衡
        if (m + n - 1) % 2 == 1: return False
        
        # 特例，grid[0][0] 是 )，不可能平衡
        if grid[0][0] == ')': return False
        
        # 特例，grid[m-1][n-1] 是 (，不可能平衡
        if grid[m-1][n-1] == '()': return False

        # 記憶化 dfs，使用 functools.cache
        # 代入坐標 (r, c)，左括號減右括號數量 balance
        @cache        
        def dfs(r, c, balance):
            # 更新左括號減右括號數量
            if grid[r][c] == '(':
                balance += 1
            else:
                balance -= 1
            
            # 剪枝，如果右括號比左括號多，不符合規則，回傳 False
            if balance < 0: return False

            # 遞迴出口，抵達終點，檢查左、右括號是否一樣多
            if r == m-1 and c == n-1:
                return balance == 0
            
            # 遞迴，向右走
            if r < m-1 and dfs(r+1, c, balance):
                return True
            
            # 遞迴，向下走
            if c < n-1 and dfs(r, c+1, balance):
                return True
            
            # 預設回傳 False
            return False
        
        # 呼叫 dfs 求答案
        return dfs(0, 0, 0)

C++ 程式碼

要使用 vector 當作 map 的 key，速度比較慢。Runtime: 50 ms, beats 86.60%. Memory: 39.75 MB, beats 46.61%.

class Solution {
private:
    int m, n;  // m 列、n 欄
    map<vector<int>, bool> memo;  // (r, c, balance): true or false

public:
    // 記憶化 dfs，代入坐標 (r, c)，左括號減右括號數量 balance
    bool dfs(int r, int c, int balance, const vector<vector<char>>& grid) {
        // 更新左括號減右括號數量
        if (grid[r][c] == '(') balance++;
        else balance--;

        // 如果 memo 之中有已經算過的結果，直接回傳
        vector<int> state = {r, c, balance};
        if (memo.count(state) == 1) {
            return memo[state];
        }

        // 剪枝，如果右括號比左括號多，不符合規則，回傳 False
        if (balance < 0) return false;

        // 遞迴出口，抵達終點，檢查左、右括號是否一樣多
        if (r == m-1 && c == n-1) {
            return balance == 0;
        }

        // 遞迴，向下走
        if (r < m-1 && dfs(r+1, c, balance, grid)) {
            memo[state] = true;
            return true;
        }

        // 遞迴，向右走
        if (c < n-1 && dfs(r, c+1, balance, grid)) {
            memo[state] = true;
            return true;
        }

        // 預設回傳 False
        memo[state] = false;
        return false;
    }

    bool hasValidPath(vector<vector<char>>& grid) {
        m = (int)grid.size();
        n = (int)grid[0].size();

        // 特例，如果總步數 m + n - 1 是奇數，不可能平衡
        if ((m + n - 1) % 2 == 1) return false;

        // 特例，grid[0][0] 是 )，不可能平衡
        if (grid[0][0] == ')') return false;

        // 特例，grid[m-1][n-1] 是 (，不可能平衡
        if (grid[m-1][n-1] == '(') return false;
        
        // 呼叫 dfs 求答案
        return dfs(0, 0, 0, grid);
    }
};