Leetcode 32. Longest Valid Parentheses (python+cpp)

题目

解法1：stack

解释参见comment

class Solution:def longestValidParentheses(self, s: str) -> int:# add -1 as the starting of a valid sequencestack = [-1]max_length = 0for i in range(len(s)):# we will push whenever we encounter '('if s[i]=='(':stack.append(i)else:# when we encounter ')', we first popstack.pop()# if the stack become empty after poping, it means the element we pop out won't be '(', which means no valid sequence is formed. So we append the current ')', which serve as the -1if len(stack)==0:stack.append(i)# if the stack is not empty after poping, it means the element we pop out must be '(', which means a valid sequence is formed, so we update the max_lengthelse:max_length = max(max_length,i-stack[-1])return max_length

C++版本
二刷写的C++版本，思路相同但是逻辑更直观

class Solution {
    
public:int longestValidParentheses(string s) {
    stack<int> st;st.push(-1);int max_len = 0;int tmp;for(int i=0;i<s.size();i++){
    if(s[i] == '('){
    st.push(i);}else{
    tmp = st.top();// if the top ind is -1 or not '(', no valid substring formed// we push the currend ind as a mark if(tmp == -1 || s[tmp] != '('){
    st.push(i);// otherwise, the top element is '(', we formed a new valid substring}else{
    st.pop();max_len = max(max_len,i-st.top());}}}return max_len;}
};

解法2：两次扫描

解释参见comment，一句话来描述就是，通过简单的count左右括号的数量，左右两次扫描中一定有一次能发现最长的valid sequence

class Solution:def longestValidParentheses(self, s: str) -> int:# from two direction, there must exist a direction that we can find the longest valid sequence by simply counting the number og '(' and ')'left = right = max_length = 0for i in range(len(s)):if s[i]=='(':left += 1if s[i]==')':right += 1if left == right:max_length = max(max_length,2*left)if right>left:left = right = 0left = right = 0for i in range(len(s)-1,-1,-1):if s[i]=='(':left += 1if s[i]==')':right += 1if left == right:max_length = max(max_length,2*left)if left>right:left = right = 0return max_length