Longest Valid Parentheses

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

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

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

参考:http://www.cnblogs.com/easonliu/p/3637429.html

 

C++ 代码实现:

#include<iostream>
#include<string>
#include<stack>
using namespace std;

class Solution
{
public:
    int longestValidParentheses(string s)
    {
        stack<int> st;
        if(s.empty())
            return 0;
        bool a[s.length()];
        size_t i;
        for(i=0; i<s.length(); i++)
        {
            if(s[i]=='(')
            {
                //还没有匹配的都设置为false
                a[i]=false;
                st.push(i);
            }
            else if(!st.empty()&&s[i]==')')
            {
                //每次匹配设置两个为true
                a[i]=true;
                a[st.top()]=true;
                st.pop();
            }
            else
                a[i]=false;
        }
        int max=0;
        int count=0;
        for(i=0; i<s.length(); i++)
        {
            if(a[i])
                count++;
            else
                count=0;
            if(count>max)
                max=count;
        }
        return max;
    }
};

int main()
{
    Solution s;
    string str="(()";
    cout<<s.longestValidParentheses(str)<<endl;
}

 

相关文章
|
canal
LeetCode 125. Valid Palindrome
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
92 0
LeetCode 125. Valid Palindrome
Leetcode-Easy 20. Valid Parentheses
Leetcode-Easy 20. Valid Parentheses
108 0
Leetcode-Easy 20. Valid Parentheses
[LeetCode]--20. Valid Parentheses
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid. The brackets must close in the correct order, “()” and “()[]{}” are a
1290 0
LeetCode - 32. Longest Valid Parentheses
32. Longest Valid Parentheses  Problem's Link  ---------------------------------------------------------------------------- Mean:  给定一个由'('和')'组成的字符串,求最长连续匹配子串长度.
973 0
LeetCode - 20. Valid Parentheses
20. Valid Parentheses  Problem's Link  ---------------------------------------------------------------------------- Mean:  给定一个括号序列,检查括号是否按顺序匹配.
876 0