算法-面试题系列(一)➡️题目三➡️子串最长括号有效配对
括号有效配对是指:
- 任何一个左括号都能找到和其正确配对的右括号
- 任何一个右括号都能找到和其正确配对的左括号
给定一个字符串,返回一个括号字符串中,最长的括号有效子串的长度。
题解思路:
定义一个数组,子串中,以index为结尾,最长的有效配对长度为Len;
- 求dp[3]的答案分析
public static int maxLength(String s) {
if (s == null || s.length() < 2) {
return 0;
}
char[] str = s.toCharArray();
int[] dp = new int[str.length];
int pre = 0;
int ans = 0;
// dp[0] = 0;
for (int i = 1; i < str.length; i++) {
if (str[i] == ')') {
pre = i - dp[i - 1] - 1; // 与str[i]配对的左括号的位置 pre
if (pre >= 0 && str[pre] == '(') {
dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
}
}
ans = Math.max(ans, dp[i]);
}
return ans;
}