DFS_leetcode.22.括号生成

发表于 | 分类于 ， | 热度: ℃
字数统计: 2.1k | 阅读时长 ≈ 9

🌸题目

🍁字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

1
2
3
4
5
6
7
8
输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

🌸解法一：暴力DFS

我们可以生成所有$ 2^{2n}$ 个 '(' 和 ')' 字符构成的序列，然后我们检查每一个是否有效即可。

为了生成所有序列，我们可以使用递归。长度为 n 的序列就是在长度为 n-1 的序列前加一个 ‘(‘ 或 ‘)’。

为了检查序列是否有效，我们遍历这个序列，并使用一个变量 balance 表示左括号的数量减去右括号的数量。如果在遍历过程中 balance 的值小于零，或者结束时 balance 的值不为零，那么该序列就是无效的，否则它是有效的

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
public static List<String> generateParenthesis(int n){
	List<String> res = new ArrayList<>();
	dfs(new char[2 * n], 0, res);
	return res;
}
private static void dfs(char[] cur, int pos, List<String> res) {
	// TODO Auto-generated method stub
	if(pos == cur.length) {
		if(valid(cur)) {
			res.add(new String(cur));
		}
	}else {
		cur[pos] = '(';
		dfs(cur, pos + 1, res);
		cur[pos] = ')';
		dfs(cur, pos + 1, res);
	}
}
private static boolean valid(char[] cur) {
	int balance = 0;
	for(char c : cur) {
		if(c == '(') {
			balance++;
		}else {
			balance--;
		}
		if(balance < 0) {
			return false;
		}
	}
	return balance == 0;
}

python

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
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def generate(A):
            if len(A) == 2*n:
                if valid(A):
                    ans.append("".join(A))
            else:
                A.append('(')
                generate(A)
                A.pop()
                A.append(')')
                generate(A)
                A.pop()

        def valid(A):
            bal = 0
            for c in A:
                if c == '(': bal += 1
                else: bal -= 1
                if bal < 0: return False
            return bal == 0

        ans = []
        generate([])
        return ans

🌸解法二： DFS剪枝

  • 当前左右括号都有大于 0个可以使用的时候，才产生分支；

  • 产生左分支的时候，只看当前是否还有左括号可以使用；

  • 产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支

  • 在左边和右边剩余的括号数都等于 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
32
33
34
35
36
37
public static List<String> generateParenthesis2(int n){
	List<String> res = new ArrayList<>();
	//特判
	if(n == 0) {
		return res;
	}
	//回溯
	dfs2("", n, n, res);
	return res;
}
/**
 * 
 * @param cur 当前递归得到的结果
 * @param left 左括号还有几个可以使用
 * @param n 右括号还有几个可以使用
 * @param res 结果集
 */
private static void dfs2(String cur, int left, int right, List<String> res) {
	// TODO Auto-generated method stub
	//因为每一次尝试，都使用新的字符串变量，所以无需回溯
	//在递归结束的时候，直接把他添加到结果集即可，
	if(left == 0 && right == 0) {
		res.add(cur);
		return;
	}
	
	//剪枝（左括号可使用个数严格大于右括号使用个数，才剪枝）
	if(left > right) {
		return;
	}
	if(left > 0) {
		dfs2(cur + "(", left - 1, right, res);
	}
	if(right > 0) {
		dfs2(cur + ")", left, right - 1, res);
	}
}

python

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
from typing import List


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        res = []
        cur_str = ''

        def dfs(cur_str, left, right):
            """
            :param cur_str: 从根结点到叶子结点的路径字符串
            :param left: 左括号还可以使用的个数
            :param right: 右括号还可以使用的个数
            :return:
            """
            if left == 0 and right == 0:
                res.append(cur_str)
                return
            if right < left:
                return
            if left > 0:
                dfs(cur_str + '(', left - 1, right)
            if right > 0:
                dfs(cur_str + ')', left, right - 1)

        dfs(cur_str, n, n)
        return res

🌸解法三： DFS剪枝（做加法）

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 static List<String> generateParenthesis3(int n){
	List<String> res = new ArrayList<>();
	//特判
	if(n == 0) {
		return res;
	}
	//回溯
	dfs3("", 0, 0, n, res);
	return res;
}
/**
 * 
 * @param cur 当前递归得到的结果
 * @param left 左括号已经用了几个
 * @param n 左括号、右括号一共得用几个
 * @param res 结果集
 */
private static void dfs3(String cur, int left, int right, int n, List<String> res) {
	// TODO Auto-generated method stub
	//因为每一次尝试，都使用新的字符串变量，所以无需回溯
	//在递归结束的时候，直接把他添加到结果集即可，
	if(left == n && right == n) {
		res.add(cur);
		return;
	}
	
	//剪枝（左括号可使用个数严格大于右括号使用个数，才剪枝）
	if(left < right) {
		return;
	}
	if(left < n) {
		dfs3(cur + "(", left + 1, right, n, res);
	}
	if(right < n) {
		dfs3(cur + ")", left, right + 1, n, 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
27
28
29
30
from typing import List


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        res = []
        cur_str = ''

        def dfs(cur_str, left, right, n):
            """
            :param cur_str: 从根结点到叶子结点的路径字符串
            :param left: 左括号已经使用的个数
            :param right: 右括号已经使用的个数
            :return:
            """
            if left == n and right == n:
                res.append(cur_str)
                return
            if left < right:
                return

            if left < n:
                dfs(cur_str + '(', left + 1, right, n)

            if right < n:
                dfs(cur_str + ')', left, right + 1, n)

        dfs(cur_str, 0, 0, n)
        return res

🌸解法四： BFS

广度优先遍历，得自己编写结点类，显示使用队列这个数据结构。深度优先遍历的时候，就可以直接使用系统栈，在递归方法执行完成的时候，系统栈顶就把我们所需要的状态信息直接弹出，而无须编写结点类和显示使用栈。

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
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> generateParenthesis4(int n) {
    List<String> res = new ArrayList<>();
    if (n == 0) {
        return res;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.offer(new Node("", n, n));
    // 总共需要拼凑的字符总数是 2 * n
    n = 2 * n;
    while (n > 0) {
        int size = queue.size();
        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 - 1，故 “可能的括号对数” 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
// 把结果集保存在动态规划的数组里

public List<String> generateParenthesis5(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);
}

@题解来自liweiwei

最后，不经历风雨,怎能在计算机的大山之顶看见彩虹呢！ 无论怎样，相信明天一定会更好！！！！！

-------------本文结束感谢您的阅读-------------
云澈 wechat
扫一扫，用手机访问哦
坚持原创技术分享，您的支持将鼓励我继续创作！
0%