Lexi's Leetcode solutions

[leetcode] Longest Valid Parentheses | ()))(())..这种括号组合,最长的valid括号组合有多长

Posted on: October 19, 2013

括号题也不是只用stack才能做,这题是算长度,所以stack那种一match就俩一起pop了的方式就不适合了。求极值,一维dp最好使。

  • d[i]: 以i开头的最长valid parentheses有多长。
  • d[i] =
    • if  (str[i] == ‘)’),以右括号开头必定invalid,d[i] = 0
    • if (str[i] == ‘(‘),以左括号开头
      1. 我们想看对应的有木有右括号。因为d[i + 1]代表的sequence肯定是左括号开头右括号结尾,所以我们想catch((…))这种情况。j = i + 1 + d[i + 1],正好就是str[i]后面越过完整sequence的下一个,若是右括号,d[i] = 2 + d[i + 1]
      2. 除此之外,还有包起来后因为把后面的右括号用了而导致跟再往后也连起来了的情况,如((..))()()()。所以d[i]还要再加上j后面那一段的d[j + 1]

这个定义和最长公共字串那题的定义类似,都是“以某个固定位置开始/结束”。看两头的方式又像palindrome。从后往前的一维dp也不常见。挺好玩的,一下复习好多东西。

public int longestValidParentheses(String s) {
    if (s.length() == 0)
        return 0;
    int maxLen = 0;
    int[] d = new int[s.length()];
    // d[i] means substring starts with i has max valid lenth of d[i]
    d[s.length() - 1] = 0;
    for (int i = s.length() - 2; i >= 0; i--) {
        if (s.charAt(i) == ')')
            d[i] = 0;
        else {
            int j = (i + 1) + d[i + 1];
            if (j < s.length() && s.charAt(j) == ')') {
                d[i] = d[i + 1] + 2; //(()())的外包情况
                if (j + 1 < s.length())
                    d[i] += d[j + 1];//()()的后面还有的情况
            }
        }
        maxLen = Math.max(maxLen, d[i]);
    }
    return maxLen;
}

—————————-用stack的做法———————————–

  1. stack里面装的一直是“还没配好对的那些可怜的括号的index”
  2. 是'(‘的时候push
  3. 是’)’的时候,说明可能配对了;看stack top是不是左括号,不是的话,push当前右括号
  4. 是的话,pop那个配对的左括号,然后update res:i和top的(最后一个配不成对的)index相减,就是i属于的这一段的当前最长。如果一pop就整个栈空了,说明前面全配好对了,那res就是最大=i+1
public int longestValidParentheses(String s) {
    int res = 0;
    Stack<Integer> stack = new Stack<Integer>();
    char[] arr = s.toCharArray();
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == ')' && !stack.isEmpty() && arr[stack.peek()] == '(') {
            stack.pop();
            if (stack.isEmpty())
                res = i + 1;
            else
                res = Math.max(res, i - stack.peek());
        } else {
            stack.push(i);
        }
    }
    return res;
}
Advertisements

6 Responses to "[leetcode] Longest Valid Parentheses | ()))(())..这种括号组合,最长的valid括号组合有多长"

Thanks very much!
这是我见过的最简洁的这道题的解法了,我用了两个stack
dp也很有启发~
非常谢谢

Glad to help 🙂

class Solution
{
public:
int longestValidParentheses(string s){
stack ss;
int len=s.size();
int result=0,accu=0;
for (int i=0;i<len;i++){
if (s[ss.top()]=='(' && !ss.empty() && s[i]==')' ){
ss.pop();
if (ss.empty()){
result= i+1;
}
else{
result= max(i-ss.top(),result);
}
}
else{
ss.push(i);
}
}

return result;
}
};
用c++写了一下,就不通过,何解?

非常感谢!
dp非常有启发!
但第一种方法是不是有点小问题,当j>s.length()的时候,没有对d[i]进行赋值,这个时候d[i]应该是0. 或者刚开始的时候把d全部赋值为0

Let n = s.length(), it can be proved that when j == n or s.charAt(j) == ‘(‘, then d[i] = 0. This is important because when we wrote c++ code, d[i] may not be initialized by zero. So it would be more rigorous to add a branch:
if (j < s.length() && s.charAt(j) == ')') {

} else {
d[i] = 0;
}

After the following line
int[] d = new int[s.length()];
is executed, all element of d have been initialized to zero. So there’s no need to add else { d[i]=0 }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: