美文网首页
LeetCodeDay51 —— 括号生成★★☆

LeetCodeDay51 —— 括号生成★★☆

作者: GoMomi | 来源:发表于2018-06-06 14:31 被阅读0次

22. 括号生成

描述
  • 给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
示例
  给出 n = 3,生成结果为:
    [
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]
思路
  1. 暴力法,利用回溯列出全排列,然后筛选其中符合条件的组合返回。思路较为简单,但效率比较低。不过其中回溯算法的写法和判断括号是否有效要掌握。
  2. 仔细思考暴力法中回溯的过程,很多时候在添加‘('或者')'的时候就已经能够知道是否合法了,所以应该只回溯合法的组合,回溯到最后即可加入到结果集中:
    1)对于数字 n,一共有 n 个 '(' 和 n 个')'
    2)对于结果集中的一个位置str[i],左括号总是可以加入的(只要还有剩余),而右括号只有在前面有多余的左括号的情况下才可以加入。因此可以利用一个 notCouple 变量记录未配对的个数,加入左括号时+1,加入右括号时-1。
    3)接口设计为helper(当前位置,总长度,剩余左括号数,剩余右括号数,当前未配对数,当前字符串,结果集)
class Solution_22_01 {
 public:
  vector<string> generateParenthesis(int n) {
    if (n < 1) return {};
    string str = "";
    vector<string> ret;
    _generateParenthesis(0, n * 2, str, ret);
    return ret;
  }
  void _generateParenthesis(int n, int size, string& str, vector<string>& ret) {
    if (n == size) {
      if (isValidBracket(str)) ret.push_back(str);
      return;
    }
    str.push_back('(');
    _generateParenthesis(n + 1, size, str, ret);
    str.pop_back();
    str.push_back(')');
    _generateParenthesis(n + 1, size, str, ret);
    str.pop_back();
  }
  bool isValidBracket(string str) {
    stack<char> ms;
    for (char ch : s) {
      if (ch == '(')
        ms.push(ch);
      else if (ch == ')') {
        if (ms.empty() || ms.top() != '(') return false;
        ms.pop();
      }
    }
    return ms.empty();
  }
};

class Solution_22_02 {
 public:
  vector<string> generateParenthesis(int n) {
    if (n < 1) return {};
    vector<string> ret;
    string str;
    helper(0, n * 2, n, n, 0, str, ret);
    return ret;
  }
  void helper(int n, int size, int left, int right, int notCouple, string& str,
              vector<string>& ret) {
    if (n == size) {
      ret.push_back(str);
      return;
    }
    if (left > 0) {
      str.push_back('(');
      helper(n + 1, size, left - 1, right, notCouple + 1, str, ret);
      str.pop_back();
    }
    if (right > 0 && notCouple > 0) {
      str.push_back(')');
      helper(n + 1, size, left, right - 1, notCouple - 1, str, ret);
      str.pop_back();
    }
  }
};

相关文章

  • LeetCodeDay51 —— 括号生成★★☆

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

  • LeetCode-22. 括号生成

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

  • HJ77 火车进站

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

  • 括号生成 (有效括号)

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

  • 括号生成

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

  • 括号生成

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

  • 括号生成

    题目来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/gene...

  • 括号生成

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

  • 括号生成

    题目需求 /*** 给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。* ...

  • 生成括号

    版权声明:本文为博主原创文章,转载请注明出处。个人博客地址:https://yangyuanlin.club欢迎来...

网友评论

      本文标题:LeetCodeDay51 —— 括号生成★★☆

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