美文网首页
LeetCode22. 括号生成

LeetCode22. 括号生成

作者: 24K纯帅豆 | 来源:发表于2019-09-18 19:19 被阅读0次

1、题目链接

https://leetcode-cn.com/problems/generate-parentheses/

2、解题思路

这道题意思是给你一个数N,然后让你返回所有的包含N对括号的有效括号组合,可能有人要问了,什么是有效括号组合,看看官方的测试用例:

当N=3时:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

估计看了也看不出个所以然来,好吧,解释一下什么是有效括号组合:

1、左括号必须用右括号闭合。
2、左括号必须以正确的顺序闭合。

总而言之,遍历整个字符串数组,当你遇到一个左括号时,把它加入一个栈中,当你遇到一个右括号时(栈中不能没有左括号),将栈中的左括号出栈,当最后数组遍历完成之后栈中没有元素,这就是一个有效的括号组合,那么我们怎么找这些有效的括号组合呢?首先一个有效的括号组合肯定是左括号开头的,这个是毫无疑问的,而且左括号和右括号是一样多的,都是N,初始状态时我们先放一个左括号,然后递归添加左右括号,那么怎么保证取到右括号的时候栈里面一定有左括号呢,任何时候左括号的数量一定是大于等于右括号的,要不然就不能保证当你取到右括号的时候栈里面一定有左括号,基于这个想法,于是就有了下面的代码:

3、代码

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        int left = 0;
        int right = 0;
        if (n != 0) {
            dfs(result, n, "(", "", left, right);
        }
        return result;
    }
    
    public void dfs(List<String> result, int n, String parentheses, String current, int left, int right) {
        // 递归搜索的终止条件,左括号=右括号
        if (left == right && left == n) {
            // 去重
            if (!result.contains(current)) {
                result.add(current);
            }
            return;
        }
        // 递归搜索的终止条件,当右括号数量大于左括号数量时,不会构成有效括号对
        if (left > n || right > n || right > left) {
            return;
        }
        current += parentheses;
        if (parentheses.equals("(")) {
            left++;
        } else {
            right++;
        }
        dfs(result, n, "(", current, left, right);
        dfs(result, n, ")", current, left, right);
    }
}

4、结果

1568803187160.jpg

相关文章

  • leetcode22. 括号生成

  • leetcode22.括号生成

    一道典型的回溯,可以使用以下2种方法: 生成所有的情况,判断每种情况是否符合题意 限定生成括号的类型,必须保证左括...

  • LeetCode22. 括号生成

    1、题目链接 https://leetcode-cn.com/problems/generate-parenthe...

  • leetcode22.括号生成

    题目链接 题目描述: 思路:递归 分析如下: 在生成括号组合的字符串时,最左边的一定是左括号。 什么时候可以生成右...

  • LeetCode22.括号生成 JavaScript

    给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。 例如,给出n = 3,...

  • LeetCode-22. 括号生成

    参考:第7课-泛型递归、树的递归 LeetCode-22. 括号生成 22. 括号生成 数字 n 代表生成括号的对...

  • HJ77 火车进站

     火车进站问题等同于括号生成[1]。 BM60 括号生成。 给出n对括号,请编写一个函数来生成所有的由n对括号组成...

  • 括号生成 (有效括号)

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

  • 括号生成

    给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。 例如,给出 n = 3...

  • 括号生成

    描述:给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。 例如,给出 n ...

网友评论

      本文标题:LeetCode22. 括号生成

      本文链接:https://www.haomeiwen.com/subject/wkikuctx.html