By Zhang, Cheng

更新日期:

文章目录
  1. 1. Longest Valid Parentheses

Longest Valid Parentheses

问题是找出一个由’(‘和’)’组成的字符串中最长可匹配的()字符串，比如’(()’就会返回2，’(()))’就会返回4。

我的方法是用栈来记录子串开始的下标。比如对)()()，栈会记录第一个)，接着当找到可以匹配的()时，子串的距离就是当前)的下标-子串开始的下标。在记录过程中，会记录最大值。

比如字符串是((())，我也需要去记录第一个(，那如果字符串是(())，那么记录的第一个(实际上是-1，-1是我预先压入栈中的。

整个计算过程是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
stack<int> st; //记录字符串开始的位置
st.push(-1);
for(int i=0;i<s.size();i++)//遍历字符串
	如果遇见的字符是(，
		那么压入栈中；
	如果遇到的字符是)，
		判断栈是否存在和它匹配的(，可以通过判断栈的大小来实现
		存在匹配，则先将匹配的(弹出
			获取子串的开始位置的上一个位置用来计算子串长度
			更新最大值
		如果不匹配，之前不存在(
			那么弹出不匹配的元素
			压入当前元素的下标
返回最大值
文章目录
  1. 1. Longest Valid Parentheses