Abo

括号(Parentheses)匹配算法题

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


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;
}

如果只有圆括号,这样就能正确判断合法性。对于三种括号的情况,我一开始想模仿这个思路,定义三个变量left1left2left3分别处理每种括号,虽然要多写不少 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. 前面括号抵消之后剩下起手右括号,还是不合法,例如:()())(

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

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

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

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

}

}