leetcode 32 Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()"

题目地址：leetcode Longest Valid Parentheses

题目大意：给你一个括号组成的字符串，要求求出最长的合法括号长度

一开始想，每次计算的时候用当前右括号，合法长度的开头，但是有

)(((((()())()()))()(()))( 应该为22. 而我合法长度的开头从1开始，因为后面没有匹配第一个和第二个左括号的，所以wa了。

后来开了个数组Match，用来标记当前左括号和哪个右括号匹配。

之后进行一次扫描，过程主要如下：

• 用temp标记合法连续的上一块总长度
• 若match[i]!=0, 每次i移动的位置直接移动到右括号的位置（即match[i])，因为这一段必定是合法的。
• 更新ans

 

class Solution {
public:
	int longestValidParentheses(string s) {
		stack<int> q;
		int len = s.length();
		int *match = new int[len];

		for (int i = 0; i < len; i++){
			match[i] = 0;
			if (s[i] == ')' && !q.empty()){
					match[q.top()] = i;
					q.pop();				
			}
			else if (s[i] == '(')
				q.push(i);
		}

		int temp = 0, ans = 0;
		for (int i = 0; i < len; i++){
			if (!match[i])	continue;
			
			if (temp + match[i] - i + 1> ans)
				ans = temp + match[i] - i + 1;
			
			if ( match[i] + 1 < len && match[ match[i] + 1] == 0)
				temp = 0;
			else
				temp = temp + match[i] - i + 1;
			i = match[i];
		}

		delete[] match;
		return ans;
	}
};

 

之后搜了别人怎么做的。

有的直接用个bool数组标记括号是否匹配，如果匹配为1，之后进行统计即可。 更简单一些。

参考代码如下：

c++:

class Solution {
public:
	int longestValidParentheses(string s) {
		stack<int> q;
		int len = s.length();
		bool *match = new bool[len];

		for (int i = 0; i < len; i++){
			match[i] = 0;
			if (s[i] == ')' && !q.empty()){
					match[q.top()] = match[i]=true;
					q.pop();				
			}
			else if (s[i] == '(')
				q.push(i);
		}

		int temp = 0, ans = 0;
		for (int i = 0; i < len; i++){
			if (!match[i])	{ temp = 0; continue; }
			temp++;
			ans = ans < temp ? temp : ans;		
		}

		delete[] match;
		return ans;
	}
};

Python

class Solution:
    # @param s, a string
    # @return an integer
    def longestValidParentheses(self, s):
        stack=[]
        match=[0 for i in range(0,len(s))]
        for i,c in enumerate(s):
            if c == '(':
                stack.append(i)
            elif c==')' and len(stack)!=0:
                match[i]=match[stack[-1]]=1
                stack.pop()
        
        ans ,temp=0,0    
        for i,c in enumerate(match):
            if match[i]:
                temp=temp+1
                ans= max(ans,temp)
            else:
                temp=0
        return ans

 

还可以用栈记录上一个括号的位置和之前连续的长度。

若能和上一段拼接起来，就合并。合并比(())()这种情况，最后一个)的时候，发现可以和之前的合并。

class Solution {
public:
	int longestValidParentheses(string s) {
		int ans = 0, cur = 0;
		stack<pair<int, int>> q;
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == ')') {
				if (q.empty())
					cur = 0;
				else {
					pair<int, int> t = q.top();
					cur += t.second + 2;
					q.pop();
					if (!q.empty() && q.top().first == i - cur + 1) {
						cur += q.top().second;
						q.pop();
					}
					ans = max(ans, cur);
				}
			}
			else {
				q.push(make_pair(i,cur));
				cur = 0;
			}
		}
		return ans;
	}
};

 

下面是最简洁的写法了，

• 遇到(就把下标放入，

• 遇到)就先pop一个，

  • 如果栈为空，说明没匹配，把当前下标push进去，作为新的一段的开始
  • 栈不为空，说明合法，长度为i - 栈顶的下标

class Solution {
public:
	int longestValidParentheses(string s) {
		int ans = 0, cur = 0;
		stack<int> q;
		q.push(-1);
		for (int i = 0; i < s.size(); ++i) {
			if (s[i] == ')') {
				q.pop();
				if (q.empty())
					q.push(i);
				else
					ans = max(ans, i - q.top());
			}
			else {
				q.push(i);
			}
		}
		return ans;
	}
};