Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
簡(jiǎn)單說(shuō)一下題意：
給定一個(gè)只包含"("或")"的字符串液肌，找到括號(hào)格式正確的最長(zhǎng)子字符串的長(zhǎng)度蘸劈，比如輸入為"(()"時(shí)胧后，輸出為2，輸入為")()())"輸出為4科盛。
此問(wèn)題肯定需要遍歷所有字符帽衙，遍歷到一個(gè)")"時(shí)盡量利用前面獲取到的信息進(jìn)行配對(duì)，如果前面有能夠匹配的到的"("贞绵，這里“能夠匹配的到的”的意思是離其最近的沒(méi)有配對(duì)的"("厉萝，那么根據(jù)前面的信息計(jì)算出當(dāng)前位置最長(zhǎng)有效子字符串的長(zhǎng)度。計(jì)算的方法是：
我們使用n表示索引(0開(kāi)始)，f(n)表示n位置字符參與的能夠配對(duì)的子字符串長(zhǎng)度冀泻，那么上一個(gè)沒(méi)有配對(duì)的'('的位置為n - f(n-1) -2：
IMG_20180621_171404.jpg
根據(jù)推導(dǎo)公式實(shí)現(xiàn)的代碼：
public class LongestValidParentheses {
public static void main(String[] args) {
System.out.println(new LongestValidParentheses()
.longestValidParentheses2("()(())"));
}
int longestValidParentheses2(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int[] lengthArr = new int[s.length()];
int max = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')' && i - lengthArr[i - 1] - 1 >= 0 && s
.charAt(i - lengthArr[i - 1] - 1) == '(') {
lengthArr[i] = lengthArr[i - 1] + 2 + (i - lengthArr[i - 1] -
2 > 0 ? lengthArr[i - lengthArr[i - 1] - 2] : 0);
}
max = Math.max(max, lengthArr[i]);
}
return max;
}
}
看到有的解決方案是創(chuàng)建一個(gè)s.length()+1的數(shù)組，0位置為保留位置蜡饵，這樣就不用判斷“i - lengthArr[i - 1] - 2 > 0”了弹渔。
現(xiàn)在貼上代碼：
public int longestValidParentheses(String s) {
int n = s.length();
int max = 0;
int[] dp = new int[n+1];
for(int i = 1; i <= n; i++){
if(s.charAt(i-1) == ')' && i-dp[i-1]-2 >= 0 && s.charAt(i-dp[i-1]-2) == '('){
dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2];
max = Math.max(dp[i], max);
}
}
return max;
}
