Abo

括号(Parentheses)匹配算法题

发表于 | 分类于 | 热度 ℃
字数统计 4.2k | 阅读时长 17

其中包含：广搜、深搜、动态规划


weather


        

        


递归很要命💀


判断括号的合法性
对括号的合法性判断是一个很常见且实用的问题，比如说我们写的代码，编辑器和编译器都会检查括号是否正确闭合。而且我们的代码可能会包含三种括号[](){}，判断起来有一点难度。


本文就来聊一道关于括号合法性判断的算法题，相信能加深你对栈这种数据结构的理解。


解决这个问题之前，我们先降低难度，思考一下，如果只有一种括号()，应该如何判断字符串组成的括号是否合法呢？


处理一种括号
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
public static boolean isValid(String s){
    if(s == null || s.length() < 1)
        return true;
    int n = s.length();// 字符串长度
    // 创建一个栈来装字符
    Stack<Character> stack = new Stack<>();
    // 遍历字符串
    for(int i = 0; i < n; i++){
        // 获取字符串的第 i 个字符
        char c = s.charAt(i);
        if(c == '('){
            stack.push(c);
        }else{
            if(stack.isEmpty())
                return false;
            else
                stack.pop();
        }
    }
    // 判断是否为空
    if(stack.isEmpty())
        return true;

    return false;
}


优化：


1
2
3
4
5
6
7
8
9
10
11
12
bool isValid(string str) {
    int left = 0;
    for(char c : str) {
        if(c == '(')
            left++;
        else
            left--;
        if(left < 0)
            return false;
    }
    return left == 0;
}


如果只有圆括号，这样就能正确判断合法性。对于三种括号的情况，我一开始想模仿这个思路，定义三个变量left1，left2，left3分别处理每种括号，虽然要多写不少 if else 分支，但是似乎可以解决问题。 


但实际上直接照搬这种思路是不行的，比如说只有一个括号的情况下(())是合法的，但是多种括号的情况下，[(])显然是不合法的。


仅仅记录每种左括号出现的次数已经不能做出正确判断了，我们要加大存储的信息量，可以利用栈来模仿类似的思路。


处理多种括号
栈是一种先进后出的数据结构，处理括号问题的时候尤其有用。


我们这道题就用一个名为left的栈代替之前思路中的left变量，遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isValid(string str){
    stack<char> left;
    for(char c : str) {
        if(c == '(' || c == '[' || c == '{')
            left.push(c);
        else if(!left.empty() && leftOf(c) == left.top())
            left.pop();
        return false;
    }
    return left.empty();
}


char leftOf(char c) {
    if(c == '(')
        return ')';
    else if(c == '[')
        return ']';
    return '}';
}


以上就是判断括号合法性的算法思路，核心就是利用了栈先进后出的特点，栈顶元素就是最近的左括号，遇到右括号就在栈顶判断就行了。遇到括号相关的问题，可以优先考虑一下是否能借助栈来解决。


最长有效括号
其实这道题就是 leetcode 的原题，第 32 题，难度为 hard。


1
2
3
4
5
6
7
8
9
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"


1、暴力法


暴力法其实很简单，就是最开始把第一个字符当做最长有效括号的首字符来遍历字符串，接着把第二个字符当做最长有效括号的首字符来遍历字符串，接着把第三个字符……


例如对于 s =  “( ) ) ( ( ) )”。


把第一个字符作为首字符，则 max = 2 （遇到第三个字符 ‘)’ 就匹配不了了）
把第二个字符作为首字符，则 max = 0 （一开始就是 ‘)’，显然啥也匹配不了）
把第三个字符作为首字符，则 max = 0
把第四个字符作为首字符，则 max = 4
…..
这种做法的时间复杂度为 O(n^2)，空间复杂度为 O(1)




基本上面那道题一样，只是做了 n 次遍历。




这道题的优化版本我们仍然是用栈来做，不过入栈的时候，不是让 “(“ 入栈，而是让 “(“ 的下标入栈。步骤如下：


1、先把 -1 放入栈内。（至于为什么？看到后面你就知道了）
2、、对于遇到的每个 ‘(‘ ，我们将它的下标放入栈中。
3、对于遇到的每个 ‘)’ ，我们弹出栈顶的元素并将当前元素的下标与弹出元素下标作差，得出当前有效括号字符串的长度。


通过这种方法，我们继续计算有效子字符串的长度，并最终返回最长有效子字符串的长度。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int longestValidParentheses(String s) {
    int max = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
        //下标入栈
            stack.push(i);
        } else {
        // 出栈
            stack.pop();
            // 看栈顶是否为空，为空的话就不能作差了
            if (stack.empty()) {
                stack.push(i);
            } else {
            // i - 栈顶，获得档期有效括号长度
                max = Math.max(max, i - stack.peek());
            }
        }
    }
    return maxans;
}


实际上，这道题仍然可以像上面那样，用变量来代替栈来优化，不过这个时候我们需要两个变量，我们假设变量为 left 和 right。


我们在从从左到右遍历字符串的过程中，用 left 记录 ‘(‘ 的数量，用 right 记录 ‘)’ 的数量。并且在遍历的过程中：


1、如果 left >= right，显然这个时候 right 个 ‘)’ 都将一定能够得到匹配。所以当前的有效括号长度为 2 * right。然后更新 max。


2、如果 left < right，显然这个时候部分 ‘)’ 一定得不到匹配，此时我们把 left 和 right 都置为 0。


当遍历完字符串，我们是否就得到最大长度的有效括号了呢？大家可以想一下


答是不可以的，我们还需要从右到左遍历计算一下。


为什么呢？


因为实际上 ‘(‘ 和 ‘)’ 其实是等价的，为什么就不可以倒过来遍历计算呢？所以，千万别忽略了哈。


最后的代码如下：


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
public int longestValidParentheses(String s) {
    int left = 0, right = 0, max = 0;
    // 从左到右
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            left++;
        } else {
            right++;
        }
        if (left == right) {
            max = Math.max(max, 2 * right);
        } else if( right > left) {
            left = right = 0;
        }
    }
    left = right = 0;
    // 从右到左
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == '(') {
            left++;
        } else {
            right++;
        }
        if (left == right) {
            max = Math.max(max, 2 * left);
        } else if (left > right) {
            left = right = 0;
        }
    }
    return max;
}


高频算法题：括号生成
题目描述
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。


例如，给出 n = 3，生成结果为：


1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]


回溯算法（深度优先遍历）
之后会写一篇关于深搜跟广搜的文章


如果完成一件事情有很多种方法，并且每一种方法分成若干步骤，那多半就可以使用“回溯”算法完成。


“回溯”算法的基本思想是“尝试搜索”，一条路如果走不通（不能得到想要的结果），就回到上一个“路口”，尝试走另一条路。


因此，“回溯”算法的时间复杂度一般不低。如果能提前分析出，走这一条路并不能得到想要的结果，可以跳过这个分支，这一步操作叫“剪枝”。


做“回溯”算法问题的基本套路是：


1、使用题目中给出的示例，画树形结构图，以便分析出递归结构；


一般来说，树形图不用画完，就能够分析出递归结构和解题思路。


2、分析一个结点可以产生枝叶的条件、递归到哪里终止、是否可以剪枝、符合题意的结果在什么地方出现（可能在叶子结点，也可能在中间的结点）；


3、完成以上两步以后，就要编写代码实现上述分析的过程，使用代码在画出的树形结构上搜索符合题意的结果。


在树形结构上搜索结果集，使用的方法是执行一次“深度优先遍历”。在遍历的过程中，可能需要使用“状态变量”。


我们以 n = 2 为例，画树形结构图。


1


参考代码如下：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if(n == 0)
            return res;
        dfs('',n,n,res);
        return res;
    }
    private void dfs(String curstr,int left,int right, List<String> res) {
        if(left == 0 && right == 0) {
            res.add(curstr);
            return;
        }
        if(left > 0) {
            dfs(curstr+'(', left-1, right, res);
        }
        if(right > 0 && right > left) {
            dfs(curstr+ ')', left, right-1, res);
        }

    }
}




Parentheses: 圆括号




带注释版：


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
36
37
38
public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        // 特殊情况
        if (n == 0) {
            return res;
        }
        // 执行深度优先遍历，搜索可能的结果
        dfs("", n, n, res);
        return res;
    }
    /**
     * @param curStr 当前递归得到的结果
     * @param left   左括号还有几个没有用掉
     * @param right  右边的括号还有几个没有用掉
     * @param res    结果集
     */
    private void dfs(String curStr, int left, int right, List<String> res) {
        // 因为是递归函数，所以先写递归终止条件
        if (left == 0 && right == 0) {
            res.add(curStr);
            return;
        }
        // 因为每一次尝试，都使用新的字符串变量，所以没有显式的回溯过程
        // 在递归终止的时候，直接把它添加到结果集即可，与「力扣」第 46 题、第 39 题区分
        // 如果左边还有剩余，继续递归下去
        if (left > 0) {
            // 拼接上一个左括号，并且剩余的左括号个数减 1
            dfs(curStr + "(", left - 1, right, res);
        }
        // 什么时候可以用右边？例如，(((((()，此时 left < right，
        // 不能用等号，因为只有先拼了左括号，才能拼上右括号
        if (right > 0 && left < right) {
            // 拼接上一个右括号，并且剩余的右括号个数减 1
            dfs(curStr + ")", left, right - 1, res);
        }
    }
}


因为每一次尝试，都使用新的字符串变量，所以没有显式的回溯过程


在递归终止的时候，直接把它添加到结果集即可，与leetcode第 46 题、第 39 题区分


如果我们不用减法，使用加法，即 left 表示“左括号还有几个没有用掉”，right 表示“右括号还有几个没有用掉”，可以画出另一棵递归树。


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
36
37
public class Solution {
    // 方法 2：用加法
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        // 特判
        if (n == 0) {
            return res;
        }
        // 这里的 dfs 是隐式回溯
        dfs("", 0, 0, n, res);
        return res;
    }
    /**
     * @param curStr 当前递归得到的结果
     * @param left   左括号用了几个
     * @param right  右括号用了几个
     * @param n      左括号、右括号一共用几个
     * @param res    结果集
     */
    private void dfs(String curStr, int left, int right, int n, List<String> res) {
        // 因为是递归函数，所以先写递归终止条件
        if (left == n && right == n) {
            res.add(curStr);
            return;
        }
        // 如果左括号还没凑够，继续凑
        if (left < n) {
            // 拼接上一个左括号，并且剩余的左括号个数减 1
            dfs(curStr + "(", left + 1, right, n, res);
        }
        // 什么时候可以用右边？例如，(((((()，此时 left > right，
        // 不能用等号，因为只有先拼了左括号，才能拼上右括号
        if (right < n && left > right) {
            // 拼接上一个右括号，并且剩余的右括号个数减 1
            dfs(curStr + ")", left, right + 1, n, res);
        }
    }


广度优先遍历
使用广度优先遍历，结果集都在最后一层，即叶子结点处得到所有的结果集，编写代码如下。


还是这棵树，只是我们这次使用广搜


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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class Solution {
    class Node {
        /**
         * 当前得到的字符串
         */
        private String res;
        /**
         * 剩余左括号数量
         */
        private int left;
        /**
         * 剩余右括号数量
         */
        private int right;

        public Node(String res, int left, int right) {
            this.res = res;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "res='" + res + '\'' +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node("", n, n));
        // n对括号，总共需要拼凑的字符总数是 2 * n
        n = 2 * n;
        while (n > 0) {
            int size = queue.size();
            // size记录接下来需要poll的元素个数
            for (int i = 0; i < size; i++) {
                Node curNode = queue.poll();
                if (curNode.left > 0) {
                    queue.offer(new Node(curNode.res + "(", curNode.left - 1, curNode.right));
                }
                if (curNode.right > 0 && curNode.left < curNode.right) {
                    queue.offer(new Node(curNode.res + ")", curNode.left, curNode.right - 1));
                }
            }
            n--;
        }
        // 最后一层就是题目要求的结果集
        while (!queue.isEmpty()) {
            res.add(queue.poll().res);
        }
        return res;
    }
}


动态规划
第 1 步：定义状态 dp[i]


使用 i 对括号能够生成的组合。


注意：每一个状态都是列表的形式。


第 2 步：状态转移方程：


    

  • i 对括号的一个组合，在 i - 1 对括号的基础上得到；
    • 

  • i 对括号的一个组合，一定以左括号 “(“ 开始（不一定以 “)” 结尾），为此，我们可以枚举右括号 “)” 的位置，得到所有的组合；
    • 

  • 枚举的方式就是枚举左括号 “(“ 和右括号 “)” 中间可能的合法的括号对数，而剩下的合法的括号对数在与第一个左括号 “(“ 配对的右括号 “)” 的后面，这就用到了以前的状态。
    • 



状态转移方程是：


1
dp[i] = "(" + dp[可能的括号对数] + ")" + dp[剩下的括号对数]


    

  • “可能的括号对数” 与 “剩下的括号对数” 之和得为 i，故“可能的括号对数” j 可以从 0 开始，最多不能超过 i， 即 i - 1；
    • 

  • “剩下的括号对数” + j = i - 1，故 “剩下的括号对数” = i - j - 1。
    • 



整理得：


1
dp[i] = "(" + dp[j] + ")" + dp[i- j - 1] , j = 0, 1, ..., i - 1


第 3 步：思考初始状态和输出：


初始状态：因为我们需要 0 对括号这种状态，因此状态数组 dp 从 0 开始，0 个括号当然就是 [“”]。
输出：dp[n] 。
这个方法暂且就叫它动态规划，这么用也是很神奇的，它有下面两个特点：


1、自底向上：从小规模问题开始，逐渐得到大规模问题的解集；


2、无后效性：后面的结果的得到，不会影响到前面的结果。


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
public class Solution {
    // 把结果集保存在动态规划的数组里
    public List<String> generateParenthesis(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        // 这里 dp 数组我们把它变成列表的样子，方便调用而已
        List<List<String>> dp = new ArrayList<>(n);

        List<String> dp0 = new ArrayList<>();
        dp0.add("");
        dp.add(dp0);

        for (int i = 1; i <= n; i++) {
            List<String> cur = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                List<String> str1 = dp.get(j);
                List<String> str2 = dp.get(i - 1 - j);
                for (String s1 : str1) {
                    for (String s2 : str2) {
                        // 枚举右括号的位置
                        cur.add("(" + s1 + ")" + s2);
                    }
                }
            }
            dp.add(cur);
        }
        return dp.get(n);
    }
}


n对括号能组成多少种合法括号串
题目要求：请编程计算出结果，如果数字过大，给出它对100007取模之后的结果。


    

  1. 考虑几种情况，起手右括号，怎么都不合法，例如：)(())(
    

    2. 

  2. 前面括号抵消之后剩下起手右括号，还是不合法，例如：()())(
    

    3. 

  3. 剩下的只要左右括号总个数相同，都是合法情况
    

    4. 

  4. 有点像“栈”的过程，入栈出栈
    

    5. 

  5. 我们可以用递归来实现代码，每一次都是添加左括号或者添加右括号的过程，注意递归函数的理解，看代码
    

    6. 



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
36
37
38
39
40
41
public class CountBracketPair {

    private int count(int total, int left, int right) {
        // 如果左括号用完，剩下只能填右括号，记录这种方法
        if(left == total) {
            return 1;
        }
        // 添加一个左括号，左括号在任何时候都能添加
        int leftCount = count(total, left + 1, right);
        // 添加一个右括号，注意右括号只有在比左括号少的情况下才能添加，否则就不合法
        int rightCount = 0;
        if(left > right) {
            rightCount = count(total, left, right + 1);
        }
        // 两种情况数量相加
        return leftCount + rightCount;
    }

    // total代表总共多少对括号
    public int countPair(int total) {

        // left和right表示已经使用的左括号和右括号，初始为0
        int left = 0, right = 0;

        // 递归计算结果
        return count(total, left, right);

    }
}
public class Main {

    public static void main(String[] args) {

        CountBracketPair countBracketPair = new CountBracketPair();

        System.out.println(countBracketPair.countPair(12)); //208012
        System.out.println(countBracketPair.countPair(12) % 100007); //7998

    }

}