首页 > 其他 > 详细

Longest Valid Parentheses

时间:2015-07-01 15:43:31      阅读:207      评论:0      收藏:0      [点我收藏+]

这道题好理解,但是要自己想的话还是很难想出来的,动态规划说白了就是记录当前的结果,留给后面的用。

 

求最长合法匹配的长度,这道题可以用一维动态规划逆向求解。假设输入括号表达式为String s,维护一个长度为s.length的一维数组dp[],数组元素初始化为0。 dp[i]表示从s[i]到s[s.length - 1] 包含s[i] 的最长的有效匹配括号子串长度。则存在如下关系:

  • dp[s.length - 1] = 0;
  • i从n - 2 -> 0逆向求dp[],并记录其最大值。若s[i] == ‘(‘,则在s中从i开始到s.length - 1计算dp[i]的值。这个计算分为两步,通过dp[i + 1]进行的(注意dp[i + 1]已经在上一步求解):
    • 在s中寻找从i + 1开始的有效括号匹配子串长度,即dp[i + 1],跳过这段有效的括号子串,查看下一个字符,其下标为j = i + 1 + dp[i + 1]。若j没有越界,并且s[j] == ‘)’,则s[i ... j]为有效括号匹配,dp[i] =dp[i + 1] + 2。
    • 在求得了s[i ... j]的有效匹配长度之后,若j + 1没有越界,则dp[i]的值还要加上从j + 1开始的最长有效匹配,即dp[j + 1]。
      class Solution {
      public:
          int longestValidParentheses(string s) {
            int len=s.size();
            vector<int >res(len,0);
            int finalRes=0;
            for(int i = len-2;i>=0;i--)
            {
                if(s[i]==()
                {
                     int end=i + 1 + res[i + 1];
                     if(end<len&&s[end]==))
                     {
                          res[i]=res[i+1]+2;
                          if(end+1<len)
                              res[i]+=res[end+1];
                          finalRes=max(finalRes,res[i]);
                     }
                         
                }
            }
            return finalRes;
          }
      };

       

Longest Valid Parentheses

原文:http://www.cnblogs.com/qiaozhoulin/p/4613220.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!