题目大意：
最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为"()()"
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=32
解题思路：
题意很简单，第一想法就是利用递归或者动态规划DP。我是用递归来做的，先捋一捋思路。求最长的有效括号子串长度。括号可以嵌套多层，如果内层子串不是连续有效的话，那么其父层字符串一定不是有效串。反之，如果子串是有效串，并且子串前一字符为正括号，子串后一字符为反括号，则父层也为有效串。那么如何找到子串的开始位置呢？出现括号嵌套的位置也就是子串开始的位置，换句话说，当连续出现两个正括号时，第二个正括号则为子串的开始位置，这个位置也是递归的入口。子串的递归开始后，若下一位仍是正括号，则继续递归，直到出现反括号，则找到了第一个有效子串，当出现连续两个反括号时，第一个反括号应该是子串的结尾位置，返回父层。简单来说，递归的最内层的有效子串一定是一组或者多组连续的括号对，即”()”或者”()()()()”。
再考虑一下例外情况，按照上面的逻辑，子串一定是以正括号开头，也就是开始时，当前字符为正括号，如果下一字符为反括号，则i+1，跳过反括号，继续向后匹配。直到当前字符出现反括号时，需跳出当前递归。
但是原字符串(题目给出的字符串s)则不同，当前字符为反括号时，只是代表当前有效子串的位置结束，之后还有可能存在更长子串，因此循环不能结束，还应继续向后匹配，直到字符串结束。
最后看一下完整代码：
int max = 0; // 返回结果
public int longestValidParentheses(String s) {
find(s, true, 0);
return max;
}
private int find(String s, boolean isOrigin, int startIndex) {
int count = 0; // 当前有效长度
for (int i = startIndex; i < s.length(); i++) {
char c = s.charAt(i); // 当前字符
// 当前字符为正括号
if (c == '(') {
// 如果当前字符为最后一位，退出循环。
if (i == s.length() - 1) {
break;
}
// 如果下一位字符仍是正括号
if (s.charAt(i + 1) == '(') {
// 从下一位开始递归嵌套子字符串，取得其有效长度
int childCount = find(s, false, i + 1);
// 如果有效长度为0，则结束循环。
// 注意，因为当前字符及下一位字符均为正括号，childCount为0只有一种可能
// 即是，当前位置到字符串结尾均为正括号，所以可以结束循环。
if (childCount == 0) {
break;
}
// childCount大于0，且长度为childCount的嵌套子串被正括号与反括号包围
if (i + childCount + 1 < s.length() && s.charAt(i + childCount + 1) == ')') {
// 有效长度应为原有效长度 + childCount + 2
count += (childCount + 2);
} else {
break;
}
// index跳过有效嵌套子串长度加一，继续循环。
i += (childCount + 1);
} else {
// 如果下一位字符为反括号，则找到一组括号对，count加2
count += 2;
// 跳过下一位的反括号继续循环
i += 1;
}
} else {
// [else]当前字符为反括号的情况。
// 如果是原始字符
if (isOrigin) {
// 清算当前长度后继续循环。
max = Math.max(count, max);
count = 0;
} else {
// 如果是嵌套子串，说明有效子串结束，退出循环
break;
}
}
}
max = Math.max(count, max);
return count;
}本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-32-longest-valid-parentheses解题思路分析/