一.题目描述
NC49最长的括号子串
题目链接:
https://www.nowcoder.com/practice/45fd68024a4c4e97a8d6c45fc61dc6ad?tpId=196&&tqId=37079&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
给出一个仅包含字符'('和')'的字符串，计算最长的格式正确的括号子串的长度。
对于字符串"(()"来说，最长的格式正确的子串是"()"，长度为2，例如：
(1)对于字符串")()())",来说，最长的格式正确的子串是"()()"，长度为4
(2)对于字符串"()(())"来说，最长的格式正确的子串是"()(())"，长度为6
(3)对于字符串"())()"来说，最长的格式正确的子串是"()"，长度为2
二.算法(栈)
但是通过栈，我们可以在遍历给定字符串的过程中去判断到目前为止扫描的子串的有效性，同时能得到最长有效括号的长度。具体做法是我们始终保持栈底元素为当前已经遍历过的元素中，最后一个没有被匹配的右括号的下标，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：
(1)对于遇到的每个'('，我们将它的下标放入栈中
(2)对于遇到的每个')'，我们先弹出栈顶元素表示匹配了当前右括号：
1.如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的，最后一个没有被匹配的右括号的下标。
2.如果栈不为空，当前右括号的下标减去栈顶元素即为以该右括号为结尾的最长有效括号的长度，我们从前往后遍历字符串并更新答案即可。需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的最后一个没有被匹配的右括号的下标，为了保持统一，我们在一开始的时候往栈中放入一个值为-1的元素。
class Solution {
public:
int longestValidParentheses(string s) {
int mx=0;//最长括号子串的长度
stack<int>st;
st.push(-1);//刚开始压入-1
for(int i=0;i<s.size();i++){
if(s[i]=='('){
st.push(i);
} else {
st.pop();
if(st.empty()){
st.push(i);//空栈直接放入
} else {
mx=max(mx,i-st.top());//找到最长的字符长度
}
}
}
return mx;
}
};时间复杂度：o(n),也就是遍历一次字符串就可以
空间复杂度：o(n) 需要使用栈来储存字符
优缺点：时间复杂度低且便于实现
三.算法(动态规划)
首先我们定义一个dp数组，其中第i个元素的下表为i的字符结尾的最长有效的字符串长度
对于，最优的策略,最后一定有一个元素s[i]，s[i]可能有下面两种情况:
(1)s[i]='('：这个时候，s[i]无法和之前的元素构成有效括号对，所以dp[i]=0
(2)s[i]=')'：这个时候需要面对元素来判断是否有有效括号对。
1.s[i-1]='('既组成一对有效括号，有效括号长度新增长度为2，i位置对最长有效括号长度为其2个位置的最长括号长度加上当前位置新增的2，那么dp[i]=dp[i-1]+2
2.s[i-1]='('：这种情况下，如果前面有和s[i]组成有效括号对的字符，即形如((....))，这样的话，就要求s[i−1]位置必然是有效的括号对，否则s[i]无法和前面对字符组成有效括号对。这时，我们只需要找到和s[i]配对对位置，并判断其是否是，其配对对位置为：i-dp[i-1]-1。
如果：s[i-dp[i−1]−1]='('有效括号长度新增长度2,i位置对最长有效括号长度为 i-1位置的最长括号长度加上当前位置新增的2，那么有：dp[i]=dp[i−1]+2
值得注意的是:i−dp[i−1]−1和i组成了有效括号对，这将是一段独立的有效括号序列，如果之前的子序列是形如(...) 这种序列，那么当前位置的最长有效括号长度还需要加上这一段。所以dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2
class Solution {
public:
int longestValidParentheses(string s) {
int len=s.size();
vector<int> dp(len, 0);//表示下标以i字符结尾的最长有效字符串的长度
int mx=0;//最长括号子串的长度
for(int i=1;i<len;i++) {
//如果第i位为左括号直接默认dp[i]为0
if (s[i]==')') {
if (s[i-1]=='(') {
dp[i]=2;
if (i-2>=0) {
dp[i]=dp[i]+dp[i-2];
}
} else if (dp[i-1]>0){
if ((i-dp[i-1]-1)>=0&&s[i-dp[i-1]-1]=='(') {
dp[i]=dp[i-1]+2;
if ((i-dp[i-1]-2)>=0) {
dp[i]=dp[i]+dp[i-dp[i-1]-2];
}
}
}
}
mx=max(mx,dp[i]);
}
return mx;
}
};时间复杂度：o(n)
空间复杂度：o(n) 需要开辟一维数组来存储
优缺点：时间复杂度低，而且实现起来比较简单，但是思考过程复杂
京公网安备 11010502036488号