Longest Valid Parentheses

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("(()()()()"));
	}

}