LeetCode 题解——Longest Valid Parentheses

发表于 | 分类于 | 阅读次数:
字数统计: 446 字

LeetCode 题解——Longest Valid Parentheses

题意

给定一个括号字符串，求出其中匹配的子字符串的最大长度

题解

DP

一个思路是用动态规划思想：用数组dp[i]表示以s[i]结尾的匹配子字符串的长度，这样我们可以得到状态转移方程：

其中后面一个分支表示的情况是，最后以后)跳过前面的已经能够匹配的子字符串能和其前面的(匹配

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.length(), res = 0;
        // len+1 数组，最前面一个当做0
        vector<int> dp(len+1, 0);
        for(int i=1; i<=len; i++)
        {
            if(i>1 && s[i-1] == ')' && s[i-2] == '(') dp[i]=dp[i-2] + 2;
            if(i>1 && s[i-1] == ')' && s[i-2] == ')' && s[i-dp[i-1]-2] == '(') dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2;
            res = max(res, dp[i]);
        }
        return res;
    }
};

利用栈

这种括号字符串的题目，大部分都能够用栈来解决，按照以往的思路：遇到左括号入栈、遇到右括号出栈，这样输入匹配的括号之后，栈里面的东西不多不少，如果此时我们记录，第一个入栈时的位置，那么最后一个出栈的时候就可以通过位置（index）计算其长度了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        int len = s.length();
        int res = 0;
        st.push(-1);
        for(int i=0; i<len; i++)
        {
            if(s[i] == '(')
                st.push(i);
            else
            {
                st.pop();
                // 栈为空的时候表示新的串匹配开始
                if(st.empty())
                    st.push(i);
                else
                {
                    res = max(res, i-st.top());
                }
            }
        }
        return res;
    }
};

更多LeetCode题解，欢迎查看我的GitHub项目