【Leetcode】python - [2267] Check if There Is a Valid Parentheses String Path 個人解法筆記 | 292nd LeetCode Weekly Contest (內含：Memoization 記憶化搜索筆記)

題目出處

2267. Check if There Is a Valid Parentheses String Path

難度

hard

題目分類

Array, Dynamic Programming, Matrix

2026-09-29 二刷

個人範例程式碼 - 二刷 (2026/09/29)

class Solution:
    def hasValidPath(self, grid: list[list[str]]) -> bool:
        h, w = len(grid), len(grid[0])
        table = [[set() for _ in range(w)] for _ in range(h)]
        # use set to prevent duplicate

        # early return impossible cases:
        if (h + w - 1) % 2 == 1 or grid[0][0] == ')' or grid[-1][-1] == '(':
            return False

        for i in range(h):
            for j in range(w):
                cur_possible_paths = set()
                delta = 1 if grid[i][j] == '(' else -1 # ( + 1, ) - 1

                if i == 0 and j == 0: # init case
                    cur_possible_paths.add(delta)

                # path from up and has valid path
                if i > 0:
                    for value in table[i-1][j]:
                        if value + delta >= 0:
                            cur_possible_paths.add(value + delta)

                # path from left and has valid path
                if j > 0:
                    for value in table[i][j-1]:
                        if value + delta >= 0:
                            cur_possible_paths.add(value + delta)

                table[i][j] = cur_possible_paths

        # Does final block contain 0?
        return True if 0 in table[-1][-1] else False

算法說明

概念簡單，但有點多細節要處理的題目。

首先記憶表是一開始就要建的，不然沒有方法能查上方或左方的情況（暴力解時間會爆）
2.1. 狀態可以進行簡化，由於我們重點就是要看 ( 數量有沒有比）多，所以等於我們只需要紀錄（還可以使用的數量是否 >= 0，也就是紀錄還可以配對的左括號數量。
2.2. 因此，每走到新的一格時，可以透過 +1, -1 來代表括弧的消耗
我們需要使用 set() 來紀錄所有的狀態，因為路徑可能來自各種不同的走法，就算是同一格也會有多種可能性，用 set 可以有效解決「不同路徑但同樣結果」的狀態重複問題。
(對於結果來說，路徑不重要，合法才重要，紀錄還可以用的數字即可)
最後一步是要檢查 0 是否有在 table[-1][-1] 當中，有存在表示真的找得到路徑。

在此解法裡面，我們只需要判斷有沒有可能，實際路徑可能存在多種可能性。
如果需要明確路徑，那就要再加上更多的記憶了，這解法只紀錄格子的狀態，是無法直接回推所有可能路徑的。

Time Complexity

O(mn(m+n))

mn 是掃矩陣的大小
(m+n) 是因為到該任一位置時，到 (i,j) 的路徑長固定為 i+j+1，最大為 h+w-1 (因為限定只能往右或往下)，也是我們最大能查表的搜尋數，簡化為 m+n

Space Complexity

O(mn(m+n))

mn 是矩陣的大小
(m+n) 是因為到該任一位置時，路徑總長固定為當下的 h+w-1 (因為限定只能往右或往下)，簡化為 m+n

Boundary conditions

可以先判出一些不可能的情況

h+w-1 (路徑總長固定值)，如果除 2 有餘數，則括弧不可能閉合
起點 grid[0][0] == ‘)’，出現則無法開始
終點 grid[-1][-1] == ‘(’，出現則無法結束

這些可以快速 early return

2022-05-10 一刷

個人範例程式碼 - 純 DFS (會 TLE)

DIRECTIONS = [
    (1,0),
    (0,1)
]
class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        if not grid:
            return False

        return self.dfs(grid, 0, 0, set(), [])

    def dfs(self, grid, i, j, visited, queue):
        # print(i, j, visited, queue)
        # end of recursion
        if i <mark> len(grid)-1 and j </mark> len(grid[0])-1:
            if grid[i][j] <mark> ")" and queue and queue[-1] </mark> "(":
                return len(queue) == 1 # queue is empty
            else:
                return False # not ")" or queue[-1] not "(" 

        # define and split
        ans = False
        visited.add((i, j))
        for d_x, d_y in DIRECTIONS:
            if ans == True: # Find case, early return
                continue
            if self.is_valid(grid, i+d_x, j+d_y) and (i+d_x, j+d_y) not in visited:
                if grid[i][j] == "(":
                    queue.append("(") 
                    ans |= self.dfs(grid, i+d_x, j+d_y, visited, queue)
                    queue.pop(-1) # backtracking 
                else: # ")"
                    if not queue:
                        # return False, wrong: need remove
                        continue
                    else:
                        queue.pop(-1) # pop ")"
                        ans |= self.dfs(grid, i+d_x, j+d_y, visited, queue)
                        queue.append(")") # backtracking

        visited.remove((i, j))
        return ans

    def is_valid(self, grid, i, j):
        m, n = len(grid), len(grid[0])
        return 0 <= i < m and 0 <= j < n

算法說明

矩陣搜索，很直覺想到的就是使用 dfs 去搜尋，
不過速度上會不夠，我們需要優化一下

個人範例程式碼 - DFS + Memoization

class Solution:
    def hasValidPath(self, grid: List[List[str]]) -> bool:
        self.memo = {}
        return self.dfs(grid, 0, 0, 0)

    def dfs(self, grid, i, j, cnt):
        # end of recursion
        if i <mark> len(grid)-1 and j </mark> len(grid[0])-1 and grid[i][j] == ")":
            return cnt == 1

        if not self.is_valid(grid, i, j):
            return False
        if cnt < 0:
            return False

        # define
        if grid[i][j] == "(":
            cnt += 1
        else:
            cnt -= 1

        # split
        if (i, j, cnt) in self.memo:
            return self.memo[(i, j, cnt)]


        ans = self.dfs(grid, i+1, j, cnt) or self.dfs(grid, i, j+1, cnt)
        self.memo[(i, j, cnt)] = ans
        return ans


    def is_valid(self, grid, i, j):
        m, n = len(grid), len(grid[0])
        return 0 <= i < m and 0 <= j < n

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

這個是在閱讀別人的解答後，自己重寫的解法，用 cnt 優化了 “()” 的 queue 判斷式，這個想法非常的漂亮。
另外這邊我也才注意到原題目要求的搜索方向固定只有「右」和「下」，
因此多方向的寫法其實也可以簡化得更漂亮。

判定條件

結束條件：

「i = len(grid)-1」 and 「j = len(grid[0])-1」判定結束位置在右下角
grid[i][j] = “)"，結束必須為 “)”
return cnt = 1 (我們也必須要知道的是，剩下個括弧數剛好等於 1，等於只剩「”("」)

終止條件:

當 cnt < 0 ，表示只有 “)"，retrun False
當不在範圍內時，return False

Memoization 筆記 (記憶化搜索)

Memoization 記憶化搜索是解決這個 TLE 的關鍵，
簡單來說就是我們把「重複性」且「已經解過的問題」，做解答的筆記。

如果說，DFS 是從起點往終點搜尋
Memoization，就是類似從終點往回看的過程紀錄 (類似 DP 概念)

以下面的圖片來說明，可能路線可能有非常多種，
但我們可以知道只要到「特定座標」，且「特定 cnt」，
就是一個重複性的題目，我們可以先把結果記錄下來。

下面看圖應該會更明顯，我們用兩種不同的路線都抵達了 (2, 2)，
而我們只需要計算第一次，之後就直接從 memo 找結果，不用再計算了。

【Leetcode】python - [2267] Check if There Is a Valid Parentheses String Path 個人解法筆記 | 292nd LeetCode Weekly Contest (內含：Memoization 記憶化搜索筆記)

你可能會想問，這樣我們怎麼省時間的?

上面我們是用 True 為舉例比較好懂，
但他更可以替我們省下大量的 False 的時間，
因為我們也能夠以同樣概念的做 (2, 2, 0) = False (我隨便舉例的，理論上不可能)
這樣我們第二次碰到 (2, 2, 0) 這題目時 (從不同路線抵達此處，也呈現同樣狀態)，
就可以不用再往下重搜了，直接回傳 False。