括号生成算法
2023-06-10 #括号生成 #DFS

LeetCode 上的括号生成问题

问题描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：["((()))", "(()())", "(())()", "()(())", "()()()"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决思路和代码

可以用 dfs 方法，递归解决：

class Solution {

    private List<String> ans;

    public List<String> generateParenthesis(int n) {
        this.ans = new ArrayList<>();
        dfs(n, n, "");
        return this.ans;
    }

    public void dfs(int left, int right, String preAns) {
        if (left == 0 && right == 0) {
            this.ans.add(preAns);
            return;
        }
        if (left > 0) {
            dfs(left-1, right, preAns+"(");
        }
        if (right > left) {
            dfs(left, right-1, preAns+")");
        }
    }
}

具体思路为：

  • left, right 分别表示当前可用的左括号和右括号
  • 如果 left > 0，那么可以在当前位置插入一个左括号
  • 如果 right > left 那么可以在当前位置插入一个右括号，这里判断条件是right > left 表示，一个有效的括号序列中，从左到右，任何位置之前的部分，不可能右括号多于左括号。

注：以上代码中，为了便于理解，每次调用 dfs() 生成了一个新的字符串，这个地方可以用可变的StringBuilder 进行优化，如果用了 StringBuilder，每次调用后，应该删除刚刚添加的字符，然后再进行下次调用，这样就是回溯的思路。

一种更复杂的括号生成问题

问题描述

编写一个函数以生成 n 个小括号和 m 个大括号，要求输出格式正确的括号的所有组合。
例如：
给定 n = 1, m = 1
输出为：({}), (){}, {()}, {}()
给定 n = 2, m = 1
输出为：["(({}))", "((){})", "(()){}", "({()})", "({}())", "({})()", "()({})", "()(){}", "(){()}", "(){}()", "{(())}", "{()()}", "{()}()", "{}(())", "{}()()"]

解决思路和代码

模仿上面只有小括号的解法，写出以下代码：

class Solution {

    private List<String> ans;

    public List<String> generateParenthesis(int n, int m) {
        this.ans = new ArrayList<>();
        dfs(n, n, m, m, "");
        return this.ans;
    }

    public void dfs(int nLeft, int nRight, int mLeft, int mRight, String seq) {
        if (nLeft == 0 && nRight == 0 && mLeft == 0 && mRight == 0 && isValid(seq)) {
            ans.add(seq);
            return;
        }
        if (nLeft > 0) {
            dfs(nLeft - 1, nRight, mLeft, mRight, seq + "(");
        }
        if (mLeft > 0) {
            dfs(nLeft, nRight, mLeft - 1, mRight, seq + "{");
        }
        if (nRight > nLeft) {
            dfs(nLeft, nRight - 1, mLeft, mRight, seq + ")");
        }
        if (mRight > mLeft) {
            dfs(nLeft, nRight, mLeft, mRight - 1, seq + "}");
        }
    }

    public boolean isValid(String s) {
        List<Integer> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(' || s.charAt(i) == '{') {
                stack.add(i);
            }
            if (s.charAt(i) == ')') {
                if (stack.isEmpty() || s.charAt(stack.get(stack.size() - 1)) != '(') {
                    return false;
                } else {
                    stack.remove(stack.size() - 1);
                }
            }
            if (s.charAt(i) == '}') {
                if (stack.isEmpty() || s.charAt(stack.get(stack.size() - 1)) != '{') {
                    return false;
                } else {
                    stack.remove(stack.size() - 1);
                }
            }
        }
        return true;
    }
}

直接套用之前的思路，会有一个问题，就是这样组合出来的序列，所有小括号组成的子序列是有效的，所有大括号组成的子序列也是有效的，但是组合在一起可能是无效序列，比如 ({)}，我目前想到的解决办法是，当用完所有括号后，生成的序列额外判断一次有效性，这样代码功能是完备的，但是感觉额外增加的复杂度有点多，目前暂时没有想到更好的解决办法。

上一页
下一页