LeetCode 32. 最长有效括号（栈&DP）
LeetCode 32. 最长有效括号（栈&DP）
Michael阿明
发布于 2021-02-20 11:00:33
发布于 2021-02-20 11:00:33
1. 题目信息
给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-valid-parentheses 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 栈 解题
括号匹配一般都可以用栈解决，这题是把相关的元素的下标出入栈
- 先把 -1push入栈
- 遇见（ ，push其下标入栈
- 遇见 ），先弹栈后，如果栈不为空，则匹配了，匹配长度count为当前 i-top，记录最大的count即为答案
- 如果栈为空，就把未匹配的 ）下标压栈
class Solution
{
public:
int longestValidParentheses(string s)
{
int count = 0, maxlen = 0;
stack<int> stk;
stk.push(-1);
for(int i = 0; i < s.size(); ++i)
{
if(s[i] == '(')
{
stk.push(i);
}
else // s[i] == ')'
{
stk.pop();
if(!stk.empty())
{
count = i-stk.top();
if(count > maxlen)
maxlen = count;
}
else
stk.push(i);
}
}
return maxlen;
}
};3. 动态规划 解题
dp[i]表示包含第下标 i 个字符的情况下，该子串匹配的最大长度
- 当
s[i] = '('时，这个子串肯定没有匹配，记dp[i] = 0，所以dp数组初始化为0 - 所以我们只要更新
s[i] = ')'时的dp[i]的值
分两种情况
s[i] = ')'&&s[i-1] = '('，那说明 dp[i] = dp[i-2] + 2s[i] = ')'&&s[i-1] = ')'，在字符 i-1处，匹配了dp[i-1] 个字符，那么再往前一个字符的下标 k 是 i-1-dp[i-1]，
- 检查s[k]，如果其为 ‘(’ ，那么下标 i 元素跟 s[k] 匹配了，再检查下 k - 1处的匹配长度 dp[k]，需要把他也加起来，则 dp[i] = dp[i-1] + dp[k-1] + 2，如果 k-1 < 0，则忽略 dp[k-1] 项
- 如果 s[k] 为 ‘)’，那么下标 i 元素与 s[k] 未匹配，则包含 s[i]的子串是不匹配的，所以 dp[i] = 0（已初始化0，不必更新dp数组）
class Solution
{
public:
int longestValidParentheses(string s)// DP解法
{
if(s.size() <= 1)
return 0;
int dp[s.size()];
int maxlen = 0, k, i;
memset(dp,0,s.size()*sizeof(int));
for(i = 1; i < s.size(); ++i)
{
if(s[i] == ')')
{
if(s[i-1] == '(')
{
if(i >= 2)
dp[i] = dp[i-2] + 2;
else
dp[i] = 2;
}
else// s[i-1] = ')'
{
k = i-1-dp[i-1];
if(k >= 0 && s[k] == '(')
{
if(k >= 1)
dp[i] = dp[i-1] + dp[k-1] + 2;
else
dp[i] = dp[i-1] + 2;
}
}
}
}
for(i = 0; i < s.size(); ++i)
{
if(dp[i] > maxlen)
maxlen = dp[i];
}
return maxlen;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/08/13 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
