LeetCode第32题-最长有效括号-java实现-图解思路与手撕代码

LeetCode第32题-最长有效括号-java实现-图解思路与手撕代码

---

一、题目描述

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

二、解题思路与代码实现

1.解题思路

对于最长类问题，可以考虑采用动态规划解决问题。

首先创建数组dp，遍历字符串s。

如果s(i)=('，则dp(i)=0

如果s(i)=‘)’，有两种情况：

若s(i-1)=‘(’，则

dp(i)=dp(i-1)+2
1

若s(i-1)=‘)’，且s(i-dp(i-1)-1)=‘(’，则

dp(i)=dp(i-1)+dp(i-dp(i-1)-2)+2
1

其余情况dp(i)=0。

2.代码实现

代码如下（示例）：

    private static int longestValidParentheses(String s) {
        if (s.length() <= 1) {
            return 0;
        }
        char[] ch = s.toCharArray();
        int res = 0;
        int[] dp = new int[s.length()];
        dp[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            if (ch[i] == '(') {
                dp[i] = 0;
            } else {
                if (ch[i - 1] == '(') {
                    dp[i] = i - 2 >= 0 ? dp[i - 2] + 2 : 2;
                } else {
                    if (i - dp[i - 1] - 1 >= 0 && ch[i - dp[i - 1] - 1] == '(') {
                        dp[i] =i - dp[i - 1] - 2>=0 ? dp[i - 1] + dp[i - dp[i - 1] - 2] + 2:dp[i - 1] +  2;
                    } else {
                        dp[i] = 0;
                    }
                }
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

注意：其中数组下标要先确定没有越界。

---

总结

对于最长类问题，可以使用动态规划进行求解。

动态规划题目分析的 4 个步骤：

1、确定状态
2、转移方程
根据问题定义得到
3、初始条件和边界情况
4、计算顺序