括号有效配对题型问题解法

目录

问题描述：

问题一：怎么判断一个括号字符串有效？

问题二：如果一个括号字符串无效，返回至少填几个字符能让其整体有效。

问题三：返回一个括号字符串中，最长的括号有效子串的长度。

问题四：保证括号字符串有效的前提下，求括号嵌套的深度。

---

问题描述：

        括号有效配对是指：

                1）任何一个左括号都能找到和其正确配对的右括号，

                2）任何一个右括号都能找到和其正确配对的左括号有效的：

                                (()) ()() (()()) 等无效的： (() )( 等。

问题一：怎么判断一个括号字符串有效？

        定义一个变量count，从左遍历字符串到最右，出现左括号时count加一，出现右括号时count减一。若整个字符串有效时，遍历过程中count值不会出现负值，并且最后count的值一定为0。

    public static boolean isValid(String str) {
        if (str == null || str.length() == 0) {
            return false;
        }
        char[] c = str.toCharArray();
        int n = c.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (c[i] == '(') {
                count++;
            } else {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }

问题二：如果一个括号字符串无效，返回至少填几个字符能让其整体有效。

        在上一个问题的基础上新增变量need用来统计需要添加的字符数量。在从字符串最左遍历到最右的过程中，若count出现了负值（只可能出现的负值为-1），则表明从该字符开始字符串失效，需要添加一个左括号让其变为有效值，need加一。遍历到字符串的最右时还可能count不为0，所以我们最后需要添加的字符串中还需要加上最后count中的值。

    public static int needParentheses(String str) {
        char[] c = str.toCharArray();
        int n = c.length;
        int count = 0;
        int need = 0;
        for (int i = 0; i < n; i++) {
            if (c[i] == '(') {
                count++;
            } else {
                count--;
            }
            if (count == -1) {
                need++;
                count = 0;
            }
        }
        return need + count;
    }
 
    public static int needParentheses2(String str) {
        char[] c = str.toCharArray();
        int n = c.length;
        int count = 0;
        int need = 0;
        for (int i = 0; i < n; i++) {
            if (c[i] == '(') {
                count++;
            } else {
                if (count == 0) {
                    need++;
                } else {
                    count--;
                }
            }
        }
        return need + count;
    }

问题三：返回一个括号字符串中，最长的括号有效子串的长度。

        动态规划，生成一个记录位置结尾的形成的最长子串的数组。假设我们现在求i位置的最长有效子串的长度，我们已经知道i-1位置的最长有效子串长度为l，如果此时i位置时左括号，那么此时以i位置结尾不可能形成有效子串，则有效子串长度为0，若是以右括号结尾的那么我们可以看此时从i位置向前推l的长度的前一个位置是否是一个左括号，若不是则以i位置结尾的最长子串长度为0，若是那么我们可以确定以i位置结尾的最长子串的最小长度是l+2，还能不能更长我们要看此时最少形成的子串的开头位置的前一个位置为结尾的子串的长度相加。

    public static int maxParenthesesLen(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] c = str.toCharArray();
        int n = c.length;
        int[] dp = new int[n];
        dp[0] = 0;
        int max = 0;
        for (int i = 1; i < n; i++) {
            if (c[i] == ')') {
                if (i - dp[i - 1] - 1 >= 0) {
                    dp[i] = c[i - dp[i - 1] - 1] == '(' ? dp[i - 1] + 2 : 0;
                }
                if (i - dp[i - 1] - 2 >= 0) {
                    dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

问题四：保证括号字符串有效的前提下，求括号嵌套的深度。

        一个变量count用于遍历过程中的左括号加一，右括号减一。max记录每一次遍历过程中count值，抓取到遍历过程中count的最大值。

    public static int deep(String str) {
        char[] c = str.toCharArray();
        int max = 0;
        int count = 0;
        for (int i = 0; i < c.length; i++) {
            count = c[i] == '(' ? count + 1 : count - 1;
            max = Math.max(max, count);
        }
        return max;
    }