leetcode32

以你之姓@ 2022-08-09 06:20 146阅读 0赞

leetcode32 ----------------longest valid parentheses

这道题目是找子串中最长匹配括号子串的长度，题目给的提示是动态规划，使用动态规划解题不是很熟，困扰了我很久。  
  
  
只有硬着头皮用栈来做了。

这里给出三个解法，第一个是自己撸的，后两个是为了学习的。

我的思路是：  
对于一长串括号来说，它存在两种情况：一种长串完全匹配，此时返回子串长度；一种是存在一些让串不匹配的字符，这样我们记录他们的索引，最后，夹在这些不匹配的字符的串就是匹配子串，我们索引相减即得到子串长度，再由此求出最长。  
对于第二种情况，举个例子：  
例如现在输入：”()()**(**()()()**(((**“  
其中加黑部分表示不匹配的位置，则现在我们记录他们之间的差，求出最大值，再与第一个不匹配的索引比较（排除前缀匹配情况），最终的结果就是最长匹配串长度。  
  
  
至于记录这些不匹配括号的位置就简单了：  
维护一个栈分为几种情况：  
1.左括号，压栈  
2.右括号，此时如果栈顶为左括号，则弹栈；如果为右括号或者为空，则将右括号压栈（多余的右括号也可能成为让子串不匹配的字符）  
  
代码如下：

class Solution {
    public:
    	int longestValidParentheses(string s) {
    		//维护两个栈，一个是括号，一个是索引
    		stack<char> parenthese;
    		stack<int>index;
    		int len = s.size();
    		int i;
    		for (i = 0; i < len; i++)
    		{
    			if (s[i] == '(')//左括号进栈
    			{
    				index.push(i);
    				parenthese.push(s[i]);
    			}
    			else
    			{
    				if (!parenthese.empty() && parenthese.top() == '(')//必须同时满足这两个条件，因为右括号也可以作为隔断匹配子串的字符
    				{
    					index.pop();
    					parenthese.pop();
    				}
    				else//此时将不匹配的不论是左括号还是右括号，都进栈
    				{
    					index.push(i);
    					parenthese.push(s[i]);
    				}
    			}
    		}
    		vector<int>myCount;
    		if (index.empty())//没有隔断的字符元素
    		{
    			return len;
    		}
    		while (!index.empty())//这里用容器来处理较为方便
    		{
    			myCount.push_back(index.top());
    			index.pop();
    		}
    		int maxCount = myCount[myCount.size() - 1];
    		if (myCount.size() > 1)
    		{
    			for (i = 0; i < myCount.size() - 1; i++)
    			{
    				maxCount = max(maxCount, myCount[i] - myCount[i + 1] - 1);
    			}
    		}//循环求两个不匹配元素中间隔的匹配子串长度，并求最大值
    		maxCount = max(maxCount, len - myCount[0] - 1);//排除前缀是匹配子串的情况
    		return maxCount;
    	}
    };

网上看了一个非常好的思路，时间复杂度和空间复杂度都是O(n)

[http://blog.csdn.net/linhuanmars/article/details/20439613][http_blog.csdn.net_linhuanmars_article_details_20439613]

看了思路后觉得真是厉害，所以尝试着写了一下，代码：

class Solution {
    public:
    	int longestValidParentheses(string s) {
    		int i;
    		stack<int>index;
    		int maxCount = 0;
    		int startIndex = 0;
    		for (i = 0; i < s.size(); i++)
    		{
    			if (s[i] == '(')
    			{
    				index.push(i);//左括号进栈
    			}
    			else if (s[i] == ')')
    			{
    				if (!index.empty())//非空
    				{
    					index.pop();//匹配一组弹栈
    					if (index.empty())//如果空了，说明当前匹配完成
    					{
    						maxCount = max(maxCount, i - startIndex + 1);
    					}
    					else//否则，由当前索引减去栈顶元素索引，表示弹出的元素与当前匹配右括号之间字符长度
    					{
    						maxCount = max(maxCount, i - index.top());
    					}
    				}
    				else//如果为空，说明上一组最长子串已经匹配完，startIndex滑动到下一个字符
    				{
    					startIndex = i + 1;
    				}
    			}
    		}
    		return maxCount;
    	}
    };

最后就是动态规划算法。说实话，DP一直是软肋，借这个题也是学习了一波。  
动归就要有动归方程，仔细分析这道题，动归方程可以这样描述：  
首先dp\[i\] 表示从s\[i\]往前推最长能匹配的子串，换句话说，就是到s\[i\]为止的最长匹配子串后缀。那么当对于下面几种情况进行分析：  
1.s\[i\] ==’(’ s\[i\]为左括号，dp\[i\]=0这个很好理解。  
2.s\[i\] ==’)’这就要分情况了  
a)如果s\[i-1\]是’(’说明已经完成了一次匹配，子串长度为2，但是还要加上dp\[i-2\]的大小，也就是当前匹配的这对括号前面的最长匹配长度，它们是相连的。  
b)如果s\[i-1\]是’)’这样不能匹配，则需要考虑s\[i-1-dp\[i-1\]\]的情况了，如果s\[i-1-dp\[i-1\]\]是一个左括号，则与当前右括号匹配，那么此时我们另dp\[i\]=dp\[i-1\]+2，这个2就是刚刚匹配的左右括号。最后还要把dp\[i-2-dp\[i-1\]\]值加起来，把相连的最大长度求出来。

代码：

class Solution
    {
    public:
    	int longestValidParentheses(string s) {//dp
    		int len = s.size();
    		vector<int>dp(len);
    		int maxCount = 0;
    		for (int i = 0; i < len; i++)
    		{
    			if (s[i] == '(')
    				dp[i] = 0;
    			else
    			{
    				if (i - 1 >= 0)//考虑输入"()"
    				{
    					if (s[i - 1] == '(')
    					{
    						dp[i] = 2;
    						if (i - 2 >= 0)
    						{
    							dp[i] += dp[i - 2];
    						}
    					}
    					else
    					{
    							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 - 1] - 2];
    							}
    					}
    				}
    			}
    			maxCount = max(maxCount, dp[i]);
    		}
    		return maxCount;
    	}
    };

[http_blog.csdn.net_linhuanmars_article_details_20439613]: http://blog.csdn.net/linhuanmars/article/details/20439613