【算法题解】38. 括号的生成

这篇具有很好参考价值的文章主要介绍了【算法题解】38. 括号的生成。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

这是一道 中等难度 的题
https://leetcode.cn/problems/generate-parentheses/

题目

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

示例 1:

输入:n = 3 
输出:["((()))","(()())","(())()","()(())","()()()"] 

示例 2:

输入:n = 1 
输出:["()"] 

提示:

  • 1 < = n < = 8 1 <= n <= 8 1<=n<=8

递归解法一

分两步操作,先递归生成所有可能的组合,然后判断组合中的每个值是否合法有效。

生成所有的组合
数字 n 代表生成括号的对数,那么最终生成的每一个结果中都会包含 2n 个括号。

12n 这些位置(或者说从 02n - 1 这些下标)上,每个位置的取值都是 “(” 或者 “)”

那么 n 对括号的的所有组合 g e n e r a t e A l l ( 2 n ) generateAll(2n) generateAll(2n) 就应该是在 g e n e r a t e A l l ( 2 n − 1 ) generateAll(2n - 1) generateAll(2n1) 的基础上再加上最后一个位置的取值,即 g e n e r a t e A l l ( 2 n − 1 ) + “ ( ” generateAll(2n - 1) + “(” generateAll(2n1)+( g e n e r a t e A l l ( 2 n − 1 ) + “ ( ” generateAll(2n - 1) + “(” generateAll(2n1)+( 的合集。

【算法题解】38. 括号的生成

以此类推,直到遇到边界条件 n = 0 时,返回 g e n e r a t e A l l ( 0 ) generateAll(0) generateAll(0) = {“”};

判断是否是有效的括号
判断括号是否有效可以使用栈的思路,遇到 “(” 则入栈,遇到 “)” 就将栈顶元素出栈并判断是否是“(”,如果不是那么肯定不合法直接返回 false

最后如果栈中还有没出栈的元素,那么也不是合法的组合,因为没出栈的 “(” 没有与之相对应的 “)”

相关题解有: 【算法题解】14. 有效的括号

Java 代码实现
class Solution {

    public List<String> generateParenthesis(int n) {
        if(n == 0){
            return Arrays.asList("");
        }
        
    	// 1. 生成所有可能的组合
    	// 2. 排除不合法的组合
        List<String> all = generateAll(2*n);
        
        return all.stream().filter(str -> isValid(str)).collect(Collectors.toList());
    }

    private List<String> generateAll(int size){
        if(size == 0){
            return Arrays.asList("");
        }

        List<String> all = new ArrayList();
        
        List<String> lastAll = generateAll(size - 1);
        for(String last : lastAll){
          
            all.add("(" + last);
            all.add(")" + last);
       
        }

        return all;
    }

    private boolean isValid(String str){
        Deque<Character> stack = new LinkedList<>();
        char[] ch = str.toCharArray();
       
        for(int i = 0; i < ch.length; i++){
            if(ch[i] == '('){
                stack.push(ch[i]);
            }else if(stack.isEmpty() || stack.pop() != '('){
                return false;
            }
        }

        return stack.isEmpty();

    }

   
}
Go 代码实现
func generateParenthesis(n int) []string {
    all := generateAll(2*n)
    ans := []string{}
    for _, str := range all {
        if isValid(st) {
            ans = append(ans, str)
        }
        
    }
    return ans
}

func generateAll(size int) []string {
    all := make([]string, 0)
    if size == 0 {
        all = append(all, "")
        return all
    }

    lastAll := generateAll(size - 1)
    for _, last := range lastAll {
        all = append(all, last + "(")
        all = append(all, last + ")")
    }
    return all
}

func isValid(s string) bool {
    n := len(s)
    stack := []byte{}
    for i := 0; i < n; i++ {
        if s[i] == ')' {
            if len(stack) == 0 || stack[len(stack)-1] != '(' {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }
    }
    return len(stack) == 0
}
复杂度分析

时间复杂度 O ( 2 2 n ∗ n ) O(2^{2n} * n) O(22nn), 生成所有组合的时间复杂度为 O ( 2 2 n ) O(2^{2n}) O(22n)n 为生成括号的对数。判断是否合法的时间复杂度为 O ( n ) O(n) O(n) ,总计 O ( 2 2 n ∗ n ) O(2^{2n} * n) O(22nn)

空间复杂度: O ( n ) O(n) O(n)n 为递归调用栈的深度。


递归解法二:分治

所有的合法的组合,都应该是以左括号 “(” 开头的,且后面肯定会有一个右括号 “)” 与之匹配。即所有的组合都满足 (a)b 的格式,其中 ab 可以为空或者其他任意有效的组合。

那么我们只要求的 ab 的结果,然后拼成 (a)b 就得出最终的答案了,求 ab 的结果同样是按照这个方式继续细分,还是递归的思路。

边界条件:n = 0 时,直接返回空,也可以把 n = 1 加上去,直接返回“()”

Java 代码实现
class Solution {
    private Map<Integer, List<String>> cache = new HashMap<>();

    public List<String> generateParenthesis(int n) {
        List<String> ans;
        if(cache.containsKey(n)){
            return cache.get(n);
        }
        if(n == 0){
            ans = Arrays.asList("");
        }else if(n == 1){
            ans = Arrays.asList("()");
        }else{
            ans = new ArrayList<>();
            // a + b = n - 1
            for(int a = 0; a < n; a ++){
                int b = n - 1 - a;
                List<String> aList = generateParenthesis(a);
                List<String> bList = generateParenthesis(b);
                for(String aTemp : aList){
                    for(String bTemp : bList){
                        ans.add("(" + aTemp +")" + bTemp);
                    }
                }
            }

        }

        cache.put(n, ans);
        return ans;
    }
   
}
Go 代码实现

func generateParenthesis(n int) []string {
    ans := []string{}
    if n == 0 {
        ans = append(ans, "")
        return ans;
    }
    if n == 1 {
        ans = append(ans, "()")
        return ans;
    }

    for a := 0; a < n; a++ {
        b := n - 1 - a

        aList := generateParenthesis(a)
        bList := generateParenthesis(b)

        for _, aTemp := range aList {
            for _, bTemp := range bList {
                ans = append(ans, "(" + aTemp + ")" + bTemp)
            }
        }
    }

    return ans
}

深度优先搜索

同解法一的思路一样,先生成所有可能的组合,然后再判断是否合法。不一样的是生成时使用 深度优先搜索 的思路。

递归函数:每一个位置都有 “(” 或者 “)”两个选项。

边界条件:当走到最后一个位置的时候返回。

【算法题解】38. 括号的生成

关于优化剪枝:

  1. 直接以右括号 “)” 开头的肯定都不合法,直接排除。
  2. 当生成的组合中,无论是 "(" 还是 ")" 的个数已将超过一半(n个),那么肯定是不合法的了,可以提前排除掉。
  3. 当遇到 ")" 的个数 大于 "(" 的个数时,那么多出来的那个右括号已经无法匹配了,可以提前排除掉。

关于判断合法性:
只要能走到最后,且左右括号的个数都是 n,那么肯定就是合法的,无需再判断合法性。

因为不合法的几种情况都通过剪枝剪掉了:

  1. 左右括号的个数不对,已经通过 剪枝条件2 剪掉。
  2. 左右括号个数相等的情况下,只要是不合法的,其前面的某一个时刻,必然是多出来一个右括号“)”是匹配不上的,已经通过 剪枝条件3 剪掉了。如某一时刻为 "a)" ,其中 a 是合法的组合,那么 “a)” 就已经不合法了。
Java 代码实现
class Solution {
 
    private List<String> ans = new ArrayList<>();
    private int size;

    public List<String> generateParenthesis(int n) {
        this.size = n;
        char[] ch = new char[2 * n];
        ch[0] = '(';
        int left = 1, right = 0;
        // 第一个位置肯定是 ‘(’
        dfs(ch, 1, 1, 0);
        return ans;
    }

    private void dfs(char[] ch, int index, int left, int right){
        if(left > size){
            return;
        }
        if(right > size){
            return;
        }

        if(right > left){
            return;
        }
        // 边界条件
        if(index == 2 * size){
            ans.add(new String(ch));
            return;
        }

        // 每个位置都有 2 种可能
        ch[index] = '(';
        dfs(ch, index + 1, left + 1, right);


        ch[index] = ')';
        dfs(ch, index + 1, left, right + 1);

        return;
    }   
}
Go 代码实现
var (
    ans []string
    size int
    )
func generateParenthesis(n int) []string {
    ans = []string{}
    size = n
    // 以左括号开始
    path := "("

    dfs(path, 1, 1, 0)

    return ans
}

func dfs(path string, index int, left int, right int){
    if left > size {
        return
    }
    if right > size {
        return
    }
    if(right > left){
        return
    }

    if index == (2 * size) {
        ans = append(ans, path)
    }

  
    dfs(path + "(", index + 1, left + 1, right)
    
    dfs(path + ")", index + 1, left, right + 1)

}

剪枝后优化效果非常明显。
【算法题解】38. 括号的生成

复杂度分析

时间复杂度 O ( 2 2 n ) O(2^{2n}) O(22n)。总的节点个数为 2 2 n + 1 − 1 2^{2n+1} -1 22n+11 个,除掉右半边,可以按照 2 2 n 2^{2n} 22n个计算。

空间复杂度: O ( n ) O(n) O(n)ch 数组长度为 2n,递归深度也是 2n文章来源地址https://www.toymoban.com/news/detail-486252.html

到了这里,关于【算法题解】38. 括号的生成的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 递归算法学习——电话号码的字母组成,括号生成,组合

    目录 一,电话号码的字母组合 1.题意 2.例子 3.题目接口  4.解题代码和思路 代码: 思路: 二,括号的生成 1.题意 2.例子 3.题目接口 四,解题代码和思路 1.先写代码: 2.思路 三,组合 1.题意 2.例子 3.题目接口 4.解题代码 1.题意 给定一个仅包含数字  2-9  的字符串,返回所有

    2024年02月10日
    浏览(67)
  • 每天一道leetcode:1466. 重新规划路线(图论&中等&广度优先遍历)

    n 座城市,从 0 到 n-1 编号,其间共有 n-1 条路线。因此,要想在两座不同城市之间旅行只有唯一一条路线可供选择(路线网形成一颗树)。去年,交通运输部决定重新规划路线,以改变交通拥堵的状况。 路线用 connections 表示,其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条

    2024年02月12日
    浏览(47)
  • 每天一道leetcode:433. 最小基因变化(图论&中等&广度优先遍历)

    基因序列可以表示为一条由 8 个字符组成的字符串,其中每个字符都是 \\\'A\\\' 、 \\\'C\\\' 、 \\\'G\\\' 和 \\\'T\\\' 之一。 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 例如, \\\"AACCGGTT\\\" -- \\\"AACCGGTA\\\" 就是一次基因变化。

    2024年02月12日
    浏览(39)
  • 每天一道leetcode:934. 最短的桥(图论&中等&广度优先遍历)

    给你一个大小为 n x n 的二元矩阵 grid ,其中 1 表示陆地, 0 表示水域。 岛 是由四面相连的 1 形成的一个最大组,即不会与非组内的任何其他 1 相连。 grid 中 恰好存在两座岛 。 你可以将任意数量的 0 变为 1 ,以使两座岛连接起来,变成 一座岛 。 返回必须翻转的 0 的最小数

    2024年02月12日
    浏览(52)
  • 每天一道leetcode:1306. 跳跃游戏 III(图论&中等&广度优先遍历)

    这里有一个非负整数数组 `arr`,你最开始位于该数组的起始下标 `start` 处。当你位于下标 `i` 处时,你可以跳到 `i + arr[i]` 或者 `i - arr[i]`。 请你判断自己是否能够跳到对应元素值为 0 的 **任一** 下标处。 注意,不管是什么情况下,你都无法跳到数组之外。 ``` 输入:arr = [4,

    2024年02月12日
    浏览(33)
  • 每天一道leetcode:797. 所有可能的路径(图论&中等&深度优先遍历)

    给你一个有 n 个节点的 有向无环图(DAG) ,请你找出所有从节点 0 到节点 n-1 的路径并输出( 不要求按特定顺序 ) graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节点 graph[i][j] 存在一条有向边)。 n == graph.length 2 = n = 15 0 = graph[i][j] n graph[i][j] != i (即不存

    2024年02月12日
    浏览(60)
  • 每天一道leetcode:剑指 Offer 64. 求1+2+…+n(中等&递归)

    求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等及条件判断语句(A?B:C)。 1 = n = 10000 使用递归,我们马上的想法是: 或者: 但是题目要求不能出现if、A?B:C这样的,所以,我们只能直接返回什么东西。返回什么?返回n。只不过n要进行自加

    2024年02月12日
    浏览(46)
  • 【算法题】动态规划中级阶段之最长回文子串、括号生成、跳跃游戏

    动态规划(Dynamic Programming,简称 DP)是一种解决多阶段决策过程最优化问题的方法。它是一种将复杂问题分解成重叠子问题的策略,通过维护每个子问题的最优解来推导出问题的最优解。 动态规划的主要思想是利用已求解的子问题的最优解来推导出更大问题的最优解,从而

    2024年02月12日
    浏览(43)
  • 每天一道leetcode:1129. 颜色交替的最短路径(图论&中等&广度优先遍历)

    给定一个整数 n ,即有向图中的节点数,其中节点标记为 0 到 n - 1 。图中的每条边为红色或者蓝色,并且可能存在自环或平行边。 给定两个数组 redEdges 和 blueEdges ,其中: redEdges[i] = [ai, bi] 表示图中存在一条从节点 ai 到节点 bi 的红色有向边, blueEdges[j] = [uj, vj] 表示图中存

    2024年02月13日
    浏览(37)
  • 每天一道leetcode:1926. 迷宫中离入口最近的出口(图论&中等&广度优先遍历)

    给你一个 m x n 的迷宫矩阵 maze ( 下标从 0 开始 ),矩阵中有空格子(用 \\\'.\\\' 表示)和墙(用 \\\'+\\\' 表示)。同时给你迷宫的入口 entrance ,用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。 每一步操作,你可以往 上 , 下 , 左 或者 右 移动一个格子。你不能进

    2024年02月12日
    浏览(34)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包