Given a string containing just the characters
'(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For
"(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is
")()())", where the longest valid parentheses substring is "()()", which has length = 4.A:
---------------4th pass ----split into two round, first find matching position of ')' , and then combine them
class Solution { public: int longestValidParentheses(string s) { int n = s.length(); vector<int> matched(n, -1); vector<int> stack; // stack of non matched ( for(int i =0;i<n;i++){ if(s[i] == '('){ stack.push_back(i); }else{ if(not stack.empty()){ matched[i] = stack.back(); stack.pop_back(); } } } // find the left most match int res = 0; for(int i= 0;i<n;i++){ if(matched[i] >=0){ int pre = matched[i]; if(pre-1>=0 && matched[pre-1] >=0){ pre = matched[pre-1]; } matched[i] = pre; // this need UPDATED res = max(res, i - pre + 1); } } return res; } };
直觉就是用DP算法。
把输入，从empty的情况，开始加入。来看待。
记录下来，与之匹配的left parentheses的位置。 最后，再计算总长度。
---------------------------第二遍-----------------O(n)的复杂度-----即使是（）（）的向后跳的情况，也是最多发生O(n)次------------------------
思想是： 从后向前，记录一个该点最远可以达到的距离。
以后每一个新的位置 i ，如果是‘（’ 首先找到它的match位置，(可能是 i+1 ,也可能是 farestMatch[i] +1 处） 。
找到match后，再查看是否是（）（）（）这种情况， 并且加上。
public class Solution {
public int longestValidParentheses(String s) {
if (s == null || s.length() == 0)
return 0;
int n = s.length();
int[] farestMatch = new int[n];
for (int i = 0; i < n; i++)
farestMatch[i] = -1;
// count from back, at each potision,record farest matching position
int maxLength = 0;
for (int i = n - 2; i >= 0; i--) {
if (s.charAt(i) == '(') {
// if next position does NOT has its matching
int k = i + 1;// to be next tested position
if (farestMatch[i + 1] > 0) // if i+1 position already has it
// matching
k = farestMatch[i + 1] + 1;
if (k < n && s.charAt(k) == ')') {
farestMatch[i] = k;
// now add possible ()()()() loops
while (farestMatch[i] + 1 < n && farestMatch[farestMatch[i] + 1] > 0)
farestMatch[i] = farestMatch[farestMatch[i] + 1];
maxLength = Math.max(maxLength, farestMatch[i] - i + 1);
}
}
}
return maxLength;
}
}
----------------------------3rd Pass-------------------------------------
这次是彻底的O（n)。 而不用那个while 循环。
思想是： 用一个数组，记录其到最左端match 的位置。遍历的时候，用stack，记录其前一个match的位置。 然后，每次combine前一个，即得到所有的，最长的match的长度。
public class Solution {
public int longestValidParentheses(String s) {
int res = 0, n = s.length();
int [] A = new int[n]; // remember A[i]'s furthest matching position
Arrays.fill(A,-1);
for(int i =1;i<n;i++){
if(s.charAt(i) ==')'){
int pre = i-1;
if(A[pre] >= 0) // pre position has no match
pre = A[pre]-1;
if(pre>=0 && s.charAt(pre)=='('){
A[i] = pre;
if(pre-1>=0 && A[pre-1]>=0)
A[i] = A[pre-1];
res = Math.max(res, i-A[i]+1);
}
}
}
return res;
}
}
Mistakes:
1： 当最终计算最大长度的时候， 我随手写了个 if (mostLeftMatchPos[i] > 0 ){
但是， 应该，是 if (mostLeftMatchPos[i] >= 0 ){ 的。
哎，不知道为什么，当时能那样写。
2： 开始， 当输入 为“（））的时候，陷入了死循环。
原因是当回头看到的是 与left 没有匹配的情况的时候。 光记得 update nRightMinusLeft 去了， 忘了把j的位置再减一。
3: 当计算longest的时候， 光考虑与之前的单独match了，却没有考虑输入为 “()() ”的情况。
因此，需要在for循环里加一个while语句。
Learned:
1： 不要想着， 精简代码。 重要的，是思路清楚。 最好是（只要复杂度不变） 先解决小问题。不要想着一步到位。 做正确才是最重要的。
例如，这里，刚开始，不要想着， 直接建立leftMostMatch 而，仅仅去找leftMatch即可。
至于（）（）这种情况。我们完全可以基于leftMatch数组再计算。
