Leetcode DP3 最长合法括号

2018-09-13  本文已影响0人  golfgang

题目

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

示例1:

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

示例2:

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

问题分解

  1. subproblem:每一个合法括号子串都是一个subproblem,计算每一个合法括号子串的长度即可。

  2. guess:
    '(' 到下一个点去,因为总有方法能使该'('属于最长合法括号里面。
    ')' 前面的是'(',合法(一种情况)。前面的是')',则看看前面还有等待结束的'(',有的话就合法,没有的不合法。

  3. related:用个table记录下合法子串开始位置到第i处之前的括号的状况(subproblem)。此外还要记录最长长度,也就是每次不合法了,就要刷新一次最长长度。

  4. bottom up

  5. solve the original problem

代码实现

class Solution {
public:
  int longestValidParentheses(string s) {
        int len = s.length(); 
        if(len<1)   return 0; 
        vector<int > table(len+1,0);//初始化一个table,初始值为0
        int cnt = 0; //cnt就是计数用的,记录有多少个'('等待结束
        if(s[0]=='(')   cnt++;// cnt =1
        else    cnt --; //cnt=-1
        int retMax = 0;
        for(int i=1;i<len;i++){
            if(s[i]=='('){
                if(cnt<0)   cnt=1;
                else    cnt++;
                continue;
            }
            //为')'的情况。
            cnt--;//一个'('被结束了,cnt-=1
            if(cnt>=0){ //cnt>=0的话,就说明前面都是合法的子串,<0的话在下一个i处会进行cnt重置。
                if(s[i-1]=='(') table[i+1] = table[i-1]+2; 
                else{
                    if(s[i-1-table[i]]=='(')
                        table[i+1] = table[i-1-table[i]]+2+table[i];//
                }
                if(retMax<table[i+1])   retMax = table[i+1];
            }
        }
        return retMax;
    }
};
上一篇下一篇

猜你喜欢

热点阅读