Leetcode 32. Longest Valid Parentheses

給定一個僅包含字符 ‘(‘ 和 ‘)’ 的字符串，返回最長有效（格式正確）括號子字符串的長度。

Python

方法一 : 用棧+動態規劃

如果是左括號，則把i(計數)存入stack裡，如果是右括號，則分為stack是否為空，如果為空則起始點+1，不為空則計算res最大是多少(如果是右括號，且棧為空，那麼先出棧，出棧後棧為空，那麼長度就是當前位置 - 起始位置 + 1，出棧後棧不為空，那麼長度就是當前位置 - 棧頂元素)

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        res,start,stack=0,0,[]
        
        for i in range(len(s)):
            if s[i]=="(":
                stack.append(i)
            else:
                if stack==[]:
                    start=i+1
                else:
                    stack.pop()
                    res=max(res,i-start+1) if stack==[] else max(res,i-stack[-1])
        return res

方法二 : 左右逼近

分別從左到右，右到左去求出最大的長度

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # Init
        max_len = 0
        left = 0
        right = 0
        
        # Left to right
        for w in s:
            if w == '(':
                left += 1
            else:
                right += 1
            
            if left == right:
                max_len = max(max_len, left+right)
            elif left < right:
                left = 0
                right = 0
        
        # Init
        left = 0
        right = 0
        
        # Right to left
        for w in reversed(s):
            if w == ')':
                right += 1
            else:
                left += 1
            
            if left == right:
                max_len = max(max_len, left+right)
            elif left > right:
                left = 0
                right = 0
        
        return max_len

C++

棧:

如果是'(‘，把當前位置數字放入stack，如果是’)’，則再判斷最後的最大長度

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stack;
        int m = 0;
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                stack.push(i);
            } else {
                stack.pop();   
                if (stack.empty()) {   #剛好()框起來，沒有多
                    stack.push(i);
                } else {
                    m = max(m, (i - stack.top()));  最大長度
                }
            }
        }
        return m;
    }
};

Python

C++

相關