leetcode-22:括号生成的深度优先搜索+剪枝解法分析

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

示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1
输出:["()"]

题目是括号生成,也就是最终用一个数据结构保存所有可能的有效字符串。每一个字符串的生成过程,都必然是放入了2n个括号,或者说选择2n次,每次要么选 "(" 要么选 ")" ,类似二叉树,那么最简单暴力的办法就是找出每一种选择生成方式,然后遍历每一种方式看是否有效,有效进数组,无效抛弃。这种方法的时间复杂度非常高。很明显暴力法存在大量的无效解,对于这种情况,通常可以采用动态规划,回溯或剪枝的思想来解决。这里考虑用深度优先搜索和剪枝。
括号的生成过程,可以对应一颗二叉树的建立或者遍历过程。

leetcode-22:括号生成的深度优先搜索+剪枝解法分析

  • 暴力法是建立了一颗满二叉树,然后逐个筛选有效的;

  • 观察二叉树的剪枝操作,条件很显然当x>0时就能往左走,只有x<y的时候才能往右走
    括号生成的原理:

    1. x>0就能往左走:因为只要还能放左括号,那么往字符串里再放一个左括号,字符串仍有成功匹配的可能;
    2. x<y才能往右走:隐含条件y>0,剩余的左括号更少,字符串里的左括号就更多,此时放右括号仍有匹配成功的可能性,反之,再放一个右括号立马不匹配了。
      推出了限制条件,就容易想到带条件的DFS的算法,在遍历二叉树的同时判断出不需要的节点,递归的代码
class Solution
{
  public:
    //定义一个全局的向量作为最后的输出和中间修改过程的容器
    vector<string> ans;
    vector<string> generateParenthesis (int n)
    {
        dfs(n, n, "");
        return ans;
    }
    // DFS,left表示还需要放入的左括号数量,right同理,left和right都不剩余,则str就绪
    void dfs (int left, int right, string str)
    {
        if (left == 0 && right == 0) {  //括号都放完了,str压入结果数组,返回上一层递归函数
            ans.push_back(str);
            return;
        }
        // 1.左括号还有,压入递归栈
        if (left > 0)
            dfs(left - 1, right, str + "(");
        // 2.剩余右括号比剩余左括号多,压入递归栈
        if (right > left)
            dfs(left, right - 1, str + ")");
    }
};

leetcode-22:括号生成的深度优先搜索+剪枝解法分析

上一篇:电脑如何录制 gif 动图?使用 GitCam!


下一篇:JUnit5的条件测试、嵌套测试、重复测试