[ LeetCode ] #32. Longest Valid Parentheses (最长符合符合匹配的子字符串）

2024-03-21 21:17:04

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

Example 1:

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

Example 2:

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

题意：

给定一个仅包含‘（ ’和‘ ）’的字符串s，求出s字串中满足符号匹配的最长字串的长度。

分析：

本题有多种解法。如下：

第一种，简单暴力直接遍历s的所有字串，然后返回符合符号匹配结果的最长字串的长度即可，实现只需要简单的遍历加判断即可，这里就不予实现了。
第二种，相当于前面一种的优化版，因为每一个符合条件的字串必须使以‘（’开头并以‘）’结尾，因此，可分以下步骤实现：
1. 定位到第一个‘（’的位置idx，以及最后一个‘）’的位置（也即子串可存在的有效范围），因为由题意可知符合条件的子串一定在这两个位置之间。
2. 从第一步得到的idx开始往后遍历至最后一个‘）’的位置，过程中统计‘（’ 和‘）’出现的次数记为left,right，如果出现right>left 则此位置即为从idx处开始的字串符合条件的最长字串。此时有效字串长度为 left*2，并结束当前位置的循环；否之如果出现left==right，那么说明当前位置能够完全匹配成功，但是不排除后面还能够继续匹配，因此只需要更新最大长度即可继续往后匹配。
3. 如果上面循环到最后的位置，那么说明idx处开始到结束位置即为符合条件的最长字串，后面位置的字串长度一定比idx位置处要短，所以可以结束遍历。
4. 总结以上步骤，相比第一种方法也只是省略了一些不必要的循环，但是每个循环查找的位置，都需要从头开始判断，因此也比较冗余。
第三种（DP）：根据第二种方法，每遍历到一个位置都需要重新判断从当前位置开始的最长符合条件的字串，因此会有很多重复的结算，因此导致执行效率很慢，那么此方法就是在前一位置的计算结果基础上只需要追加上当前位置的结果即可，步骤如下：
1. 初始化一个DP数组，用以记录以每个位置结尾且符合条件的最长字串，初始化为0；
2. 符合条件的字串一定是以‘（’开始，以‘）’结束，所以有以下几种情况：
  1. 当前位置为i，如果s[i]==')' and s[i-1]==‘（’，也即“ ...()”的情况，此时DP[i] = DP[i-2]+2即可；
  2. 如果s[i]==')' and s[i-1]==')'，也即“ ...)) ”的情况，那么如果 i-DP[i-1]>0 意思是以 i-1处结尾的字串不是从0开始的，也即i-1处符合条件的字串前面还有其他元素是，如果 s[i-DP[i-1] - 1]=='(' 的话也即（ “ ...( ' i-1符合条件的部分' ））...”的情况，那么DP[i] = DP[i-1] + DP[i-DP[i-1]-2] + 2; 其中i-DP[i-1]-2为以i-1结尾的字串的开头的前一个字串，相互连通构成一个更长的字串。
3. 见Code2；
第四种（Stack）：符号匹配最常用的方法就是stack了，因为可以根据栈里的元素就可以直接判断是否符合条件了。步骤如下：
1. 初始化一个栈，并先把-1压入栈，可以保证第一个元素为‘）’的情况正常处理。
2. 遍历元素，如果为‘（’ 则把相应的下标压入栈；如果为‘）’则出栈，出栈后如果栈为空即前面没有带匹配的元素了，那么也将当前的元素的下标压入栈，否则说明可以说明符合条件的字串长度即为栈顶的位置至当前的位置（i-st.top())；
3. 返回最大值即可；
4. 见Code3；

Code1

class Solution {
public:
    int longestValidParentheses(string s) {
     	int len = s.size();
        vector<int> DP(len,0);
        int maxN = 0;
        for(int i=1;i<len;++i){
            if(s[i]==')'){
                if(s[i-1]=='('){
                    DP[i] = (i>=2?DP[i-2]:0)+2;
                }else{
                    if(i-DP[i-1]>0 && s[i-DP[i-1]-1]=='('){
                        DP[i] = DP[i-1] + (i-DP[i-1]-2>=0?DP[i-DP[i-1]-2]:0)+2;
                    }
                }
                maxN = max(maxN, DP[i]);
            }
        }
        return maxN;
    }
};

Result

Runtime: 16 ms, faster than 20.69% of C++ online submissions for Longest Valid Parentheses.

Memory Usage: 10.9 MB, less than 42.41% of C++ online submissions for Longest Valid Parentheses.

Code2

class Solution {
public:
    int longestValidParentheses(string s) {
     	int len = s.size();
        vector<int> DP(len,0);
        int maxN = 0;
        for(int i=1;i<len;++i){
            if(s[i]==')'){
                if(s[i-1]=='('){
                    DP[i] = (i>=2?DP[i-2]:0)+2;
                }else{
                    if(i-DP[i-1]>0 && s[i-DP[i-1]-1]=='('){
                        DP[i] = DP[i-1] + (i-DP[i-1]-2>=0?DP[i-DP[i-1]-2]:0)+2;
                    }
                }
                maxN = max(maxN, DP[i]);
            }
        }
        return maxN;
    }
};

Result：

Runtime: 8 ms, faster than 99.04% of C++ online submissions for Longest Valid Parentheses.

Memory Usage: 10.9 MB, less than 51.58% of C++ online submissions for Longest Valid Parentheses.

Code3：

class Solution {
public:
    int longestValidParentheses(string s) {
     	stack<int> st;
        st.push(-1);
        int maxLen = 0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                st.push(i);
            }else{
                st.pop();
                if(st.empty()){
                    st.push(i);
                }else{
                    maxLen = max(maxLen, i-st.top());
                }
            }
        }
        return maxLen; 
    }
};

此方法核心主要通过使用栈，每次将匹配的两个元素直接消化掉（出栈），所以栈内最终剩余的元素就是待匹配的了，而当前位置与栈顶位置之间的距离就是符合条件的有效字串长度了。

Result：

Runtime: 8 ms, faster than 99.04% of C++ online submissions for Longest Valid Parentheses.

Memory Usage: 10.7 MB, less than 75.65% of C++ online submissions for Longest Valid Parentheses.

码农公寓

相关文章