LeetCode 解題筆記：856. Score of Parentheses

作者：王一哲
日期：2026年10月5日


LeetCode 題目連結：856. Score of Parentheses

解題想法

中等難度題。題目給一個字串 $s$，$s$ 之中只有 $(, )$，保證 $s$ 之中的括號一定成對。計分的原則為：

1. 只有 $()$ 為 1 分。
2. 多個括號對相連，將這些括號對的分數相加。
3. $(A)$，其中 $A$ 為某一組括號對，分數為 $A$ 的分數乘以 2。

例如 $((()()))$，分數為 $2 \times 2 \times (1 + 1) = 4 + 4 = 8$。討論區當中有一個目前看到最厲害的寫法，假設 $n$ 為 $s$ 的長度，$depth$ 為括號對的深度，$ans$ 為答案。用一個 for 迴圈掃過 $s$，如果 $s[i]$ 是 $($，$depth += 1$；如果 $s[i]$ 是 $)$，$depth -= 1$，如果 $s[i-1]$ 是 $($，則 $ans$ 要加上這對括號的分數 $2^{depth} = 1 << depth$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.09 MB, beats 97.89%.

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        n, depth, ans = len(s), 0, 0  # 長度，括號對深度，答案
        for i in range(n):
            if s[i] == '(':  # 左括號
                depth += 1  # 深度加 1
            else:  # 右括號
                depth -= 1  # 深度減 1
                if s[i-1] == '(':  # 外面還有括號
                    ans += (1 << depth)  # 加上這對括號的分數 2**depth
        return ans

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 7.69 MB, beats 99.92%.

class Solution {
public:
    int scoreOfParentheses(string s) {
        int n = (int)s.size(), depth = 0, ans = 0;  // 長度，括號對深度，答案
        for(int i = 0; i < n; i++) {
            if (s[i] == '(') {  // 左括號
                depth++;  // 深度加 1
            } else {  // 右括號
                depth--;  // 深度減 1
                if (s[i-1] == '(') {  // 外面還有括號
                    ans += (1 << depth);  // 加上這對括號的分數 2**depth
                }
            }
        }
        return ans;
    }
};

LeetCode 解題筆記：678. Valid Parenthesis String

作者：王一哲
日期：2026年10月4日


LeetCode 題目連結：678. Valid Parenthesis String

解題想法

中等難度題。題目給一個字串 $s$，$s$ 之中只有 $(, *, )$，其中 $*$ 可以當作 $($、$)$ 或空字串，要檢查 $s$ 之中的括號是否成對。這題下方的提示 1 是用遞迴與回溯窮舉將 $*$ 當作 $($、$)$ 或空字串所有可能的組合，但這個寫法的時間複雜度比較高，先不考慮。提示 2 是用動態規畫解題，用 $dp[i][j]$ 代表子字串 $s[i : j+1]$ 是否合法，寫法比較複雜，先不考慮。提示 3 是用堆疊記錄括號，討論區當中看起來最多人採用的是堆疊的寫法，看起來最可行。

我是用兩個堆疊 $left$、$star$，分別記錄左括號、星號於 $s$ 之中的索引值。用一個 for 迴圈依序讀取 $c = s[i]$，接下來分成 3 個狀況：

1. $c == '('$，$i$ 推入 $left$。
2. $c == '*'$，$i$ 推入 $star$。
3. $c == ')'$，優先使用 $($ 配對，如果有 $left$ 有資料，移除 $left$ 最後一項。如果沒有 $($ 可以配對，再用 $*$ 配對，如果 $star$ 有資料，移除 $star$ 最後一項。如果沒有 $($ 或 $*$ 可以配對，回傳 Fasle。

再用一個 while 迴圈處理剩下的 $($，如果 $left$ 有資料繼續執行。由於可以將 $left[-1]$ 右側的 $*$ 當作 $)$ 配對，如果 $star$ 有資料而且 $left[-1] < star[-1]$，移除 $left[-1]$ 及 $star[-1]$；如果條件不成立，回傳 False。跑完 while 迴圈之後，由於 $*$ 可以當作空字串，$star$ 不需要清空，$s$ 合法，回傳 True。

這題還有一個最極致的寫法，只用兩個整數變數 min_open、max_open，分別記錄未面對左括號可能的最少、最多數量。用一個 for 迴圈依序讀取 $s$ 的字元 $c$，接下來分成 3 個狀況：

1. $c == '('$，min_open 加 1，max_open 加 1。
2. $c == '*'$，$*$ 當作 $)$，min_open 減 1；$*$ 當作 $($，max_open 加 1。
3. $c == ')'$，min_open 減 1，max_open 減 1。

如果遇到 max_open 小於 0，右括號太多，回傳 False。如果 min_open 小於 0，前面將過多的 $*$ 當作 $)$，取部分 $*$ 當作 $($，將 min_open 歸零。跑完 for 迴圈之後，min_open 必須等於零。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.32 MB, beats 28.53%.

class Solution:
    def checkValidString(self, s: str) -> bool:
        n = len(s)  # 長度
        left = []  # 左括號於 s 之中的索引值
        star = []  # 星號於 s 之中的索引值

        for i in range(n):
            c = s[i]
            if c == '(':  # 左括號，i 推入 left
                left.append(i)
            elif c == '*':  # 星號，i 推入 star
                star.append(i)
            else:  # 右括號，優先配對左括號
                if left:  # 有左括號能配對，移除 left 最後一項
                    left.pop()
                elif star:  # 有星號能配對，移除 star 最後一項
                    star.pop()
                else:  # 沒有左括號或星號能配對，回傳 False
                    return False
        
        while left:  # 處理剩下的左括號，取右側的星號配對
            if star and star[-1] > left[-1]:
                left.pop()
                star.pop()
            else:  # 沒有可以配對的星號，回傳 False
                return False
        # 跑完上面的 while 迴圈時 left 已經清空，* 可以是空字串，star 不需要清空
        return True

ZeroJudge 解題筆記：o344.超市掃貨

作者：王一哲
日期：2026年10月3日


ZeroJudge 題目連結：o344.超市掃貨

解題想法

這題雖然被放在基礎題庫，但其實根本不是基礎題。題目給一個正整數 $t$，代表接下來有 $t$ 組測資。每組測資為 2 行，第一行是一個正整數 $n$，代表共有 $n$ 個酪梨；第二行有 $n$ 個正整數，代表 $n$ 個酪梨的大小。取一段連續的區間，分數為區間和乘以區間最小值，找出所有可能的區間中的最高分。

由於這題要取區間和，而且區間的資料不變，很直覺會想要用前綴和計算區間和。假設重量記錄於陣列 $nums$ 之中，為了結算最後一項的分數，$nums$ 長度為 $n+1$，最後一項為 $0$。前綴和陣列 $psum$ 長度則為 $n+2$，索引值向右平移一格。這題困難之處在於取區間最小值，比較快速的寫法是利用單調隊列，用一個堆疊 $st$ 記錄目前讀到的最小值於重量陣列之中的索引值。用一個 for 迴圈跑 $i = 0$ 到 $i = n-1$，裡面再用一個 while 檢查 $nums[i]$ 是否大於等於 $nums[st[-1]]$，如果條件成立，代表從 $i$ 開始對應到新的最小值，要先結算 $st[-1]$ 到 $i$ 之間的區間，區間不包含左、右端點。步驟為：

1. 區間最小值 $imin = nums[st.pop()]$
2. 移除 $st[-1]$ 之後，此時區間左端點 $left = st[-1]$，如果 $st$ 是空的則設定為 $-1$。區間右端點 $right = i$。
3. 區間和 $isum = psum[right] - psum[left + 1]$，這是因為 $psum$ 索引值向右平移一格，因此 $psum[(right - 1) + 1] = psum[right]$；要減去的是 $nums[left + 1]$ 的前一項$，因此 $psum[(left + 1) + 1 - 1] = psum[left + 1]$。
4. 更新答案 $ans = max(ans, imin * isum)$

由於答案很大，如果用 C++ 解題要用 long long，否則會溢位。

Python 程式碼

解題時間約為 0.9 s，使用記憶體約為 134.4 MB。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    t = int(data[0])
    ptr = 1
    for _ in range(t):
        n = int(data[ptr])
        ptr += 1
        # 讀取酪梨大小，最後加 0 結算測資中最後一個酪梨
        nums = list(map(int, data[ptr : ptr + n])) + [0]
        ptr += n
        
        # --- 建立前綴和陣列 ---
        psum = [0] + nums[:]
        for i in range(n+1):
            psum[i+1] += psum[i]
        
        # --- 由左向右掃，堆疊 st 為酪梨大小嚴格遞增的索引值
        ans = 0  # 答案
        st = []
        for i in range(n + 1):
            # nums[i] 是新的最小值，結算 (st[-1] ~ (i-1) 區間的值
            while st and nums[i] <= nums[st[-1]]:
                imin = nums[st.pop()]  # 區間最小值
                left = st[-1] if st else -1  # 如果 st 有值，左邊界為 st 最後一項；反之為 -1
                right = i  # 右邊界為 i
                # 用前綴和陣列取區間和，psum 陣列的索引值向右平移 1 格
                isum = psum[right] - psum[left + 1]
                ans = max(ans, imin * isum)
            # 更新完區間答案，i 加入 st
            st.append(i)
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：792. Number of Matching Subsequences

作者：王一哲
日期：2026年10月3日


LeetCode 題目連結：792. Number of Matching Subsequences

解題想法

中等難度題。題目給一個字串 $s$ 及一個字串陣列 $words$，要計算 $words$ 之中有幾個是 $s$ 的子序列 (subsecquence)。子序列是由 $s$ 刪除任意數量的字母，並且保持剩下的字母順序。由於這題的 $s$ 長度可達 $50000$，如果用雙層迴圈跑出 $s$ 所有的子序列會超時。我的作法是先用一個字典或陣列 $pos$，記錄 $s$ 之中每個字母的索引值，索引值由小到大排序。再寫一個檢測輸入的字串 $target$ 是否為 $s$ 子序列的函式 $check$，於函式中依序讀取 $target$ 的字母 $c$，用二分搜尋法從 $pos$ 對應到 $c$ 的資料中，搜尋是否有在前一個字母索引值 $pre$ 之後的字母 $c$，如果沒有就回傳 False；如果 $target$ 所有的字母都能被找到，回傳 True。

Python 程式碼

Runtime: 352 ms, beats 33.32%. Memory: 23.02 MB, beats 33.91%.

from bisect import bisect_left

class Solution:
    def numMatchingSubseq(self, s: str, words: list[str]) -> int:
        n = len(s)  # 長度
        # 各字母於 s 的索引值，用於二分搜尋法
        pos = [[] for _ in range(26)]
        for i in range(n):
            pos[ord(s[i]) - ord('a')].append(i)
        
        # 檢測 target 是否為 s 子序列的函式
        def check(target):
            pre = -1  # 前一個字母於 s 的索引值
            for c in target:
                arr = pos[ord(c) - ord('a')]  # 字母 c 於 s 的索引值
                j = bisect_left(arr, pre + 1)  # 找出大於等於 pre + 1 的索引值
                if j == len(arr):  # 沒找到，回傳 False
                    return False
                pre = arr[j]  # 更新 pre
            return True  # 都有找到，回傳 True
        
        # 檢測 words 之中的字串，計算答案
        ans = 0
        for word in words:
            if check(word):
                ans += 1
                
        return ans

Runtime: 282 ms, beats 57.13%. Memory: 23.22 MB, beats 16.90%.

from bisect import bisect_left

class Solution:
    def numMatchingSubseq(self, s: str, words: list[str]) -> int:
        n = len(s)  # 長度
        # 各字母於 s 的索引值，用於二分搜尋法
        pos = defaultdict(list)
        for i in range(n):
            pos[s[i]].append(i)
        
        # 檢測 target 是否為 s 子序列的函式
        def check(target):
            pre = -1  # 前一個字母於 s 的索引值
            for c in target:
                arr = pos[c]  # 字母 c 於 s 的索引值
                j = bisect_left(arr, pre + 1)  # 找出大於等於 pre + 1 的索引值
                if j == len(arr):  # 沒找到，回傳 False
                    return False
                pre = arr[j]  # 更新 pre
            return True  # 都有找到，回傳 True
        
        # 檢測 words 之中的字串，計算答案
        ans = 0
        for word in words:
            if check(word):
                ans += 1
                
        return ans

LeetCode 解題筆記：22. Generate Parentheses

作者：王一哲
日期：2026年10月2日


LeetCode 題目連結：22. Generate Parentheses

解題想法

中等難度題。題目給一個正整數 $n (1 \leq n \leq 8)$，要産生 $n$ 對 () 所有合法的排列方式，也就是括號必須成對。這題要用 dfs 窮舉所有可能的排列方式，並且在目前已經選到的排列方式不合法時提早剪枝，或是確定加上一個左或右括號還是合法排列方式時才遞迴。由於 $n$ 最大值只有 $8$，即使寫法效率差一點也能過關。

Python 程式碼

Runtime: 3 ms, beats 30.52%. Memory: 19.53 MB, beats 10.33%.

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        ans, path = [], []  # 答案，選到的字元

        # dfs 窮舉
        def dfs(balance):
            # 剪枝，如果 ( 比 ) 多，不合法
            if balance < 0: return

            # 剪枝，如果 ( 數量大於 n，不合法
            if balance > n: return
            
            # 遞迴出口，path 長度等於 2*n
            if len(path) == 2*n:
                # 合法的括號對，path 接成字串加入 ans
                if balance == 0:
                    ans.append("".join(path))
                return
            
            # 試著加入 ( 或 )，遞迴
            path.append('(')
            dfs(balance + 1)
            path.pop()
            path.append(')')
            dfs(balance - 1)
            path.pop()
        
        # 呼叫 dfs，從 balance = 0 開始測試
        dfs(0)
        return ans

ZeroJudge 解題筆記：f461.現金兌換點卷

作者：王一哲
日期：2026年10月2日


ZeroJudge 題目連結：f461.現金兌換點卷

解題想法

題目的意思是要從 $n$ 個數字之中，任選 $2$ 個數字相減、取絕對值，將所有組合得到的絕對值相加即為答案。但是這題的 $n$ 最大為 $100,000$，如果真的取 $2$ 個一組，組合數高達 $4,999,950,000$，硬算絕對會超時，需要找數學規律。

假設 $n$ 個數字儲存為陣列 $nums$，且數字由小到大排序，其中 $nums[i]$ 在答案之中，會被 $n - (i+1)$ 個比 $nums[i]$ 大的數字各減 $1$ 次，而 $nums[i]$ 則會對 $i$ 個比自己小的數各減 $1$ 次，因此 $nums[i]$ 對答案的貢獻為 $$ nums[i] \times [-(n-i-1)] + nums[i] \times i = nums[i] \times (2i + 1 - n) $$ 可以推論答案 $$ ans = \sum_{i = 0}^{n-1} nums[i] \times (2i + 1 - n) $$ 答案可能很大，如果用 C++ 解題記得要用 long long，否則會溢位。

這題另一個要注意的地方在於測資量極大，雖然記憶體上限為 512 MB，但是用 Python 解題時，如果用 sys.stdin.read().split() 一次讀取所有測資，並用 sys.stdout.write() 一次輸出所有答案，在最後一筆測資會遇到 MemoryError。我後來改用生成器及 next，每次只轉換一個整數，處理完一筆測資就輸出，最後一筆測資 5.9 s、24.8 MB 過關。。

Python 程式碼

通過 75% 的測資，最後一筆測資 MemoryError。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        nums = sorted(map(int, data[ptr : ptr + n]))
        ptr += n
        ans = sum((2*i + 1 - n) * nums[i] for i in range(n))
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 5.9 s，記憶體約為 25.2 MB，通過測試。

def solve():
    import sys
    
    def get_tokens():
        for line in sys.stdin:
            for part in line.split():
                yield part

    tokens = get_tokens()
    
    while True:
        try:
            n = int(next(tokens))
        except StopIteration:
            break
        
        nums = [int(next(tokens)) for _ in range(n)]
        nums.sort()
        ans = sum((2*i + 1 - n) * nums[i] for i in range(n))
        sys.stdout.write(f"{ans:d}\n")

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：20. Valid Parentheses

作者：王一哲
日期：2026年10月1日


LeetCode 題目連結：20. Valid Parentheses

解題想法

簡單題。題目給一個字串 $s$，其中只有 3 種括號 ()[]{}，要檢查 $s$ 的括號是否成對。為了在讀取到右括號時，可以很方便地讀取對應的左括號格式，先將這 3 種括號對應的關係存成 Python dict 或 C++ map。開一個堆疊 $st$，用來存放待配對的左括號。用一個 for 迴圈依序讀取 $s$ 的字元 $c$，如果 $c$ 是左括號，直接推入 $st$；如果 $c$ 是右括號，檢查 $st$ 的最後一項是否為對應的左括號，如果是就移除 $st$ 的最後一項；反之，括號不成對，回傳 Fasle。如果 $s$ 所有的括號都成對，最後 $st$ 應該是空的。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.23 MB, beats 64.57%.

class Solution:
    def isValid(self, s: str) -> bool:
        bracket = {')': '(', ']': '[', '}': '{'}  # 右括號對應的左括號
        st = []  # 存放括號用的堆疊
        for c in s:  # 依序讀取字元
            if c in "([{":  # 左括號，推入 st
                st.append(c)
            else:  # 右括號
                if st and st[-1] == bracket[c]:  # st 最後一項是對應的左括號
                    st.pop()  # 移除
                else:  # st 最後一項不是對應的左括號
                    return False  # 不合法
        # 最後 st 必須是空的
        return not st

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 8.97 MB, beats 37.05%.

class Solution {
public:
    bool isValid(string s) {
        map<char, char> bracket = {{')', '('}, {']', '['}, {'}', '{'}};  // 右括號對應的左括號
        stack<char> st;  // 存放括號用的堆疊
        for(char c : s) {  // 依序讀取字元
            if (c == '(' || c == '[' || c == '{') {  // 左括號，推入 st
                st.push(c);
            } else {  // 右括號
                if (!st.empty() && st.top() == bracket[c]) {  // st 最後一項是對應的左括號
                    st.pop();  // 移除
                } else {  // st 最後一項不是對應的左括號
                    return false;  // 不合法
                }
            }
        }
        // 最後 st 必須是空的
        return st.empty();
    }
};

ZeroJudge 解題筆記：n508.區間分割演算法練習

作者：王一哲
日期：2026年10月1日


ZeroJudge 題目連結：n508.區間分割演算法練習

解題想法

這題給一個正整數 $N$ 代表有 $N$ 場演講，接下來 $N$ 行，每行的格式皆為以下的樣子

Lecture 1: 9:10-10:00

如果演講的時段重疊，需要多用一間教室。如果某一場演講結束，另一場演講正好開始，可以使用同一間教室，不需要考慮換場的時間。要計算這 $N$ 場演講至少需要使用幾間教室。

這題困難之處在於讀取演講的開始、結束時間，因為測資不是用空格分隔時間，而是用 : 及 - 分隔時間。如果用 Python 解題，可以將字串讀進來之後，再用 split 分割字串，切出開始、結束時間的時、分，語法為

split('-')
split(':')

如果用 C++ 解題，假設演講編號，開始時間的時、分，結束時間的時、分，分別存入變數 k, ha, ma, hb, mb，則可以用 scanf 依照指定的格式讀取資料。為了避開前一行留下的換行符號， Lecture 之前要加一個空格，語法為

scanf(" Lecture %d: %d:%d-%d:%d", &k, &ha, &ma, &hb, &mb);

如果用 cin 讀取資料並存入字串 $s$，則要再從 $s$ 依序讀取字元，依照字元判斷是否需要分割資料，再將分割後的資料轉成 int 存入對應的變數之中。

接下來用掃瞄線演算法解題。為了便於排序及計算教室數量，用一個陣列 $arr$ 儲存開始、結束時間，將時間單位換成分，加入 $arr$ 的資料為

(開始時間, 1)
(結束時間, -1)

讀取完 $N$ 場演講的時間之後用 sort 由小到大排序。定義答案 $ans = 0$、目前使用的教室數量 $curr = 0$。從 $arr$ 之中依序讀取資料，更新目前同時進行的演講數量，也就是目前使用的教室數量 $curr$，再用 max 更新 $ans$。

Python 程式碼

解題時間約為 0.4 s，使用記憶體約為 47 MB。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        N = int(data[ptr])
        ptr += 3
        time = []
        for _ in range(N):
            s = data[ptr]
            ptr += 3
            a, b = s.split('-')
            ha, ma = map(int, a.split(':'))
            hb, mb = map(int, b.split(':'))
            time += [(ha * 60 + ma, 1), (hb * 60 + mb, -1)]
        time.sort()
        ans, curr = 0, 0
        for _, d in time:
            curr += d
            ans = max(ans, curr)
        result.append(f"{ans:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

LeetCode 解題筆記：1111. Maximum Nesting Depth of Two Valid Parentheses Strings

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


LeetCode 題目連結：1111. Maximum Nesting Depth of Two Valid Parentheses Strings

解題想法

中等難度題目。題目先定義有效括號字串 (valid parentheses string, VPS)，符合以下三個條件的其中一個就是 VPS。

1. 空字串
2. 兩個相連的 VPS
3. 一對括號之中包著另一個 VPS

接下來定義嵌套深度 (nesting depth)，計算原則為

1. 空字串，深度 0。
2. 兩個相連的 VPS $A, B$，取 $A, B$ 深度較大者。
3. 一對括號之中包著另一個 VPS $A$，等於 $A$ 的深度加 1。

題目給一個字串 $seq$，要將 $seq$ 分成 $A, B$ 兩個子序列，子序列可以不連續，但是不能改變元素的順序，目標是找出使 $A, B$ 嵌套深度最小的分組方法。假設 $seq$ 的長度為 $n$，則答案 $ans$ 是一個長度為 $n$ 的陣列，如果 $seq$ 之中索引值為 $i$ 的元素被分到子序列 $A$，則 $ans[i] = 1$，如果被分到子序列 $B$，則 $ans[i] = 0$。答案可能有很多組，回傳其中一組即可。

如果要讓一組括號嵌套深度最小，要盡量將深度平分到 $A, B$ 兩組，例如 $(())$ 應該要把頭、尾兩個括號分給 $A$，內側的兩個括號分繪 $B$。可以定義變數 $balance$，記錄左括號數量減去右括號數量。用一個 for 迴圈依序讀取 $seq$ 的字元 $seq[i] = c$，如果 $c$ 是 $($，先將 $balance + 1$，如果 $balance$ 是奇數，則這個字元分給 $A$，$ans[i] = 1$；如果 $balance$ 是偶數，則這個字元分給 $B$，$ans[i] = 0$。雖然這樣的分組方式，對於範例測資 2 得到的答案不一樣，不過仍然是符合要求的答案。

seq = "()(())()"
輸出: [1,1,1,0,0,1,1,1]
範例的答案: [0,0,0,1,1,0,1,1]

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.41 MB, beats 27.78%.

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> list[int]:
        balance = 0  # 左括號數量 - 右括號數量
        n = len(seq)  # 長度
        ans = [0] * n  # 答案
        # 原則，A、B 分別負擔一半的嵌套深度
        for i in range(n):
            c = seq[i]
            if c == '(':  # 左括號
                balance += 1  # 嵌套深度加 1
                ans[i] = balance % 2  # 深度奇數分給 A，偶數分給 B
            else:  # 右括號
                # 先結算目前這層深度再更新 balance
                ans[i] = balance % 2
                balance -= 1
        return ans

C++ 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 10.34 MB, beats 95.65%.

class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        int n = (int)seq.size(), balance = 0;  // 長度，左括號數量 - 右括號數量
        vector<int> ans (n, 0);  // 答案
        // 原則，A、B 分別負擔一半的嵌套深度
        for(int i = 0; i < n; i++) {
            char c = seq[i];
            if (c == '(') {  // 左括號
                balance++;  // 嵌套深度加 1
                ans[i] = balance % 2;  // 深度奇數分給 A，深度偶數分給 B
            } else {  // 右括號
                // 先結算目前這層深度再更新 balance
                ans[i] = balance % 2;  // 深度奇數分給 A，深度偶數分給 B
                balance--;
            }
        }
        return ans;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 13.05 MB, beats 50.00%.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* maxDepthAfterSplit(char* seq, int* returnSize) {
    int n = strlen(seq), balance = 0;  // 左括號數量 - 右括號數量
    *returnSize = n;  // 指定回傳陣列的大小
    int* ans = (int*)malloc(n * sizeof(int));  // 答案
    // 原則，A、B 分別負擔一半的嵌套深度
    for(int i = 0; i < n; i++) {
        char c = seq[i];
        if (c == '(') {  // 左括號
            balance++;  // 嵌套深度加 1
            ans[i] = balance % 2;  // 深度奇數分給 A，深度偶數分給 B
        } else {  // 右括號
            // 先結算目前這層深度再更新 balance
            ans[i] = balance % 2;
            balance--;
        }
    }
    return ans;
}

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)