Longest Valid Parentheses

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.

z题目是找出最长的匹配括号。

给的提示是用动态规划，但是我看了网上的，貌似都是没体现到。

我的解法是这样的：

1. 对输入字符串s,开辟int[s.length()]b

2. 从左到右对s进行入栈，当s[i]=='(' push(i)

3.当s[i]==')' b[i]=pop();

这样子就记录了所有）对应的（的位置。

4.从右向左扫描s，对i处==‘）’跳到其对应的‘（’处j=b[i]，并且看‘（’前面,即j-1是否也是个有匹配的‘）’如果是，则再跳到其匹配的‘(’处，累计长度

5.我比较笨，没有意识到，在一对匹配的‘（’，‘）’中，他们之间的括号一定是匹配的。

因此，在从右往左计算的时候，遍历s的指针只需要一直往‘）’所对应的‘（’处跳，而不是要-1来重复工作。

6.上面这个还要计算跳的位置，我对这种算两个下标之间距离，两数相减+1一直都容易算错。

网上还有另一个开辟bool[s.length()] b

对有匹配的括号对其对应的b中是true;

所以最终问题演变成查找b中最长的true串，（因为两个匹配的括号中间一定是匹配的）

这个方法跟5比起来是一样的，它的空间比5小，但是5理论上会快一点。

上代码

package leetcode;

import java.util.Stack;

public class longest_Valid_Parentheses {
	public static int longestValidParentheses(String s) {
		if ("".equals(s))
			return 0;
		Stack
  
    st = new Stack
   
    (); int t = 0; int[] tmp = new int[s.length()]; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') st.push(i); else if (s.charAt(i) == ')' && !st.isEmpty()) { tmp[i] = i - st.pop() + 1; } } int max = 0; for (int i = tmp.length - 1; i >= 0; i--) { if (tmp[i] != 0) { max = max > tmp[i] ? max : tmp[i]; int j=i-tmp[i]; while (j > 0 && tmp[j] != 0) { tmp[i] += (tmp[j]); max = max > tmp[i] ? max : tmp[i]; j = j - tmp[j]; } if(j>0)i=j+1; } } return max; } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out.println(longestValidParentheses("(()()()()")); } }