leetcode 32 最长括号匹配 题解

发表于 | 更新于

题目

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

Example 1:

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

Example 2:

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

解法一

首先观察一下这道题目，要找到最长的满足括号匹配的字串，那么首先要想到的是，什么时候是不匹配的呢？假设有一段满足匹配的字串s，如果在它之后的第一个元素是)，那么这时一定不匹配，如果是(，则可能会向后匹配。这样一来就能够想到，使用一个栈来存储字串的下标，用一个flag记录上一个不匹配的元素位置（初始设为-1）。每当遇到一个(时，存储这个下标，如果遇到)，则如果此时栈为空，记录flag，否则出栈一个元素再看栈是否为空，若为空则将此时位置与flag的差值作为长度备选，否则将此时位置减去栈顶位置作为长度备选（如(())的情况）。

实际实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int longestValidParentheses(string s) {
    if(s == "") return 0;
    stack<int> st;
    int flag = -1, length = 0;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == '('){
            st.push(i);
        }
        else{
            if(st.empty()){
                flag = i;
            }
            else{
                st.pop();
                if(st.empty()){
                    length = (i - flag > length) ? i - flag : length;
                }
                else{
                    length = (i - st.top() > length) ? i - st.top() : length;
                }
            }
        }
    }
    return length;
}

解法二

第二种方法就是使用动态规划了，维护一个dp数组，只在元素为)时赋值（只有此时可能是一段匹配字串的结束）。注意到每遇到一对()，长度可以增加2，而如果遇到))时，此时可能匹配（即((()))这种情况），这时赋给dp的值就可以用到之前计算过的值了，比如此时的位置为i，那么就取dp[i - 1] + dp[i - dp[i - 1] - 2] + 2赋给dp[i]。

具体实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int longestValidParentheses(string s) {
    if(s == "") return 0;
    vector<int> dp(s.size(), 0);
    if(s[0] == '(' && s[1] == ')'){
        dp[1] = 2;
    }
    for(int i = 2; i < s.size(); ++i){
        if(s[i] == ')'){
            if(s[i - 1] == '('){
                dp[i] = dp[i - 2] + 2;
            }
            else{
                if(i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '('){
                    if(i - dp[i - 1] - 1 == 0){
                        dp[i] = dp[i - 1] + 2;
                    }
                    else{
                        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
                    }
                }
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}