LeetCode高频题：子串权值定义为，最长有效括号子序列的长度，请你返回字符串s的所有子串权值的和是多少

LeetCode高频题：子串权值定义为，最长有效括号子序列的长度，请你返回字符串s的所有子串权值的和是多少？

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

基础知识：
【1】括号匹配问题：判断一个字符串是否为有效的括号匹配
【2】括号匹配问题：括号字符串是否有效匹配，无效的话还需要加多少个括号才能完全匹配
【3】括号匹配问题：括号字符串的最大匹配嵌入深度是多少
【4】括号匹配问题：括号字符串的有效匹配子串最大长度是多少

---

文章目录

• LeetCode高频题：子串权值定义为，最长有效括号子序列的长度，请你返回字符串s的所有子串权值的和是多少？
• • @[TOC](文章目录)
• 题目
• 一、审题
• 二、解题
• 据他们说这玩意超时，那看来要用动态规划优化一下
• 总结

题目

---

一、审题

示例：如上，注意是子序列，不是子串哦，子串超级困难【看上面【4】，非常重要】

---

二、解题

分析
())())

你看看这个有效子序列最长的咋搞

其实你中途给统计左括号有几个？left个
然后遇到右括号，如果left>0，则可以消耗一个left括号，配对为一对，right=1记录了
如果遇到右括号，发现left<=0，显然没有办法配对，right就不要增加了

最长的有效括号子序列长度就是right的2倍，因为配对呗

所以
你只需要遍历给你的字符串s的每一个子串，查上面的最长有效子序列长度，把结果加ans就行

手撕代码：

public static class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            String s = in.nextLine();//())())
            int ans = 0;
            for (int i = 0; i < s.length(); i++) {
                for (int j = i; j < s.length(); j++) {
                    ans += f(s.substring(i, j + 1));
                }
            }
            System.out.println(ans);
        }

        //最长括号子序列长度
        public static int f(String s){
            int l = 0, r = 0;
            char[] str = s.toCharArray();
            for (int i = 0; i < str.length; i++) {
                if (str[i] == '(') l++;
                else if (l > 0) {
                    l--;
                    r++;
                }
            }
            return r << 1;
        }
    }

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
27
28

测试：

看看朋友们今天京东的秋招笔试题目好像也不难吧？

据他们说这玩意超时，那看来要用动态规划优化一下

我想了一个方法，就是设计一个dp表

n*n

代表啥意思？dpij是代表字符串s的i–j范围上的最长括号子序列长度
可不就是一个范围上的尝试模型

那么
我们就可以这样填一个表格了
（1）主对角线全0，为啥呢？就i一个字符，没法匹配啊，长度肯定是0
（2）副对角，i必须是左括号（，j必须是右括号），同时成立，dpi，i+1 = 2

剩下的，按照上面圈1,2，3，–从下往上，每次从左往右去填

最后把右上角所有结果加到ans，相当于就是把所有子串枚举一遍

就是结果

只可惜：
（3）你咋填dpij呢？转移方程不好搞啊

比如：i是)，j是(，肯定不行，则dpij=dpi+1,j-1

比如：i是(，j是)，肯定能行，则dpij=dpi+1,j-1 + 2

但是请问别的情况呢
i=),j=)
i=(,j=(
这俩情况咋整啊？

首先看：i=(,j=(
i是(，你得看看i+1–j里面有没有)，多余了才能配对，要是不多，咋搞呢？？？？尴尬，

目前我还不知道我这么尝试对不对？
后面重新思考思考
尴尬
没完成的代码：
有大佬瞅瞅怎么改进？

public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            String s = in.nextLine();//())())
            int ans = 0;

            int n = s.length();
            char[] str = s.toCharArray();
            int[][] dp = new int[n][n];//范围L--R上的最长有效括号子序列匹配长度
            //主对角线i=j，那些格子默认0，就一个字符，咋可能有效呢？
            for (int i = 0; i < n - 1; i++) {//副对角线
                dp[i][i + 1] = str[i] == '(' && str[i + 1] == ')' ? 2 : 0;
            }
            for (int i = n - 3; i >= 0; i--) {//倒回来填写
                for (int j = i + 2; j < n; j++) {
                    //如果i是)，不行，如果j是(，不行
                    if (str[i] == ')' && str[j] == '(') {
                        dp[i][j] = dp[i + 1][j - 1];
                    }else if (str[i] == '(' && str[j] == ')'){
                        //如果i是(，且j是)，长度+2
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }else {
                        //如果i是(，可能跟i+1--j配上，长度+2
                        //如果j是)，可能跟i--j-1配上，长度+2
                        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]) + ?;????
                    }
                }
            }
            //刷一遍子串结果
            for (int i = 0; i < s.length(); i++) {
                for (int j = i; j < s.length(); j++) {
                    ans += dp[i][j];
                }
            }
            System.out.println(ans);
        }
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
27
28
29
30
31
32
33
34
35

---

总结

提示：重要经验：

1）括号匹配问题，我多次讲过，这是最新的最长有效括号子序列长度，简单，那个最长有效括号子串很难
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。