Noob
0%

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.

https://leetcode.com/problems/longest-valid-parentheses/

解法一

使用一个栈保存字符串中字符的下标，扫描字符串，如果字符串与栈顶元素指向的字符配对，则弹出栈顶元素，并计算当前坐标与当前栈顶元素之间的距离，该距离即为当前匹配字符串长度。如果不匹配则将当前字符下标压入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int longestValidParentheses(String s) {
    if(s == null) return 0;
    
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);
    
    int result = 0;
    for(int i = 0; i < s.length(); ++i) {
        int top = stack.peek();
        if(s.charAt(i) == ')' && top != -1 && s.charAt(top) == '(') {
            stack.pop();
            result = Math.max(result, i - stack.peek());
        } else
            stack.push(i);
    }
    return result;
}

解法二

使用动态规划，用一个数组longest记录已经匹配的结果，longest[i]表示以i结尾的字串中最长匹配长度。每次计算longest[i]时，需要加上包含在匹配括号内部的长度，以及加上匹配括号左边的长度。当s[i] == ‘)’ && s[i - longest[i - 1] - 1] == ‘(‘ 时发生转移，转移方程为：
longest[i] = longest[i - 1] + 2; (i - longest[i-1] - 2 < 0)
longest[i] = longest[i - 1] + 2 + longest[i - longest[i - 1] - 2]; (i - longest[i-1] - 2 >= 0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int longestValidParentheses(String s) {
    if(s == null) return 0;
    
    int result = 0;
    int[] longest = new int[s.length()];
    for(int i = 1; i < s.length(); ++i) {
        int left = i - longest[i - 1] - 1;
        if(s.charAt(i) == ')' && left >= 0 && s.charAt(left) == '(') {
            longest[i] = longest[i - 1] + 2 + (left - 1 >= 0 ? longest[left - 1] : 0);
            result = Math.max(result, longest[i]);
        }
    }
    
    return result;
}