主題

LeetCode - 32. Longest Valid Parentheses 解題心得

Not In My Back Yard | 2021-05-14 00:00:07 | 巴幣 2 | 人氣 52

題目連結:


題目意譯:
給定一字串其只包含字元 '(' 和 ')',找到最長合法(合乎格式的)括號子字串之長度。

限制:
0 ≦ s.length ≦ 3 × 10 ^ 4
s[i] 為 '(' 或是 ')'。



範例測資:
範例 1:
輸入: s = "(()"
輸出: 2
解釋: 最長的合法括號子字串為 "()"。

範例 2:
輸入: s = ")()())"
輸出: 4
解釋: 最長的合法括號子字串為 "()()"。

範例 3:
輸入: s = ""
輸出: 0


解題思維:
定義一陣列 D,其中 D[i] 代表以 s[i] 為結尾可以往左到哪使得這整段子字串為一個合法括號子字串,因此這段子字串的長度恰好為 D[i]。

因此當 s[i] 為 '(' 時, D[i] 之值為 0 ;

當 s[i] 為 ')' 且 s[i - D[i - 1] - 1] = '(' 時,代表我們可以配對 s[i - D[i - 1] - 1] 和 s[i] 形成一對括號
中間(如果 D[i - 1] ≠ 0,則為 s[i - D[i - 1]] ~ s[i - 1] 這段;反之為空)也是合法的括號子字串。因此
D[i] = D[i - D[i - 1] - 2] + D[i - 1] + 2

而其他情況下, D[i] 之值也是為 0 (因為無法湊出合法的括號)。

因為有了遞迴式,所以我們可以按照其他動態規劃(Dynamic Programming)的題目求出所有 D[i] 之值。而其中的 D[i] 最大值即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作