Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Longest Valid Parentheses

Leetcode algorithms 第 32 题:Longest Valid Parentheses。

题目

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.

解答

这种括号匹配的问题一般使用动态规划进行解决。使用dp[i]表示从位置i开始的最长合法括号序列的长度,考虑第i个位置的括号:

  • 如果是右括号,则dp[i] = 0,因为第一个是右括号是没有合法匹配
  • 如果是左括号,则考虑下一个位置i+1的情况,事实上,这是dp[i+1]的问题,可以以同样方法解决。之后可以知道第i位该匹配的位置为i+dp[i+1]+1的位置,直接判断其是否匹配即可。

注意做括号匹配到其对应的右括号时,后面可能还有左括号以继续匹配。

具体代码如下:

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size(), ans = 0;
        vector<int> dp(n, 0); //dp[i]表示从i开始的最长合法括号序列
        for (int i = n - 2; i >= 0; i--)
        {
            if (s[i] == '(') //第一个括号必须为左括号
            {
                int j = i + dp[i+1] + 1; //匹配该左括号的位置
                if (j < n && s[j] == ')')//满足匹配
                {
                    dp[i] = dp[i+1] + 2; 
                    if (j + 1 < n) dp[i] += dp[j + 1]; //后面可能还有
                    ans = max(ans, dp[i]);
                }
            }
        }
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论