Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Medium 22. Generate Parentheses

tags: leetcode

問題

$n$組のかっこが与えられた時に, 全ての適切なかっこの組み合わせを全て生成する関数を作れ

解法(recursive)

左右のかっこの個数がそれぞれ$n$個である文字列を生成するという問題です

下のように空の文字列に()を繋げて文字列を作ります

このとき, 左右かっこを繋げる動作を再帰的に定義できます

  • ここでは左のかっこの数と右のかっこの数をそれぞれlnum, rnumとします
  • lnumの左かっことrnumの右かっこからできる文字列をcur_strとします
    • 基底はcur_strの長さが入力の$n$の2倍になったとき(lnumrnumがそれぞれ$n$個のとき)です
  • では基底に合わせて左右かっこの数が揃うように文字列を生成すれば良いです
  • 上の図を見ると右のかっこは左のかっこより少ない時に文字列に連結されます
  • 左のかっこは$n$まで連結します

以上から下のようにコードを書くことが可能です

Python

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
      ans = []
      def helper(lnum = 0, rnum = 0, cur_str = ""):
        if len(cur_str) == 2 * n:
          ans.append(cur_str)
          return
        if lnum < n:
          helper(lnum + 1, rnum, cur_str + '(')
        if rnum < lnum:
          helper(lnum, rnum + 1, cur_str + ')')
      
      helper()
      return ans

C++

class Solution {
public:
  vector<string> generateParenthesis(int n) {
    vector<string> ans;
    helper(n, 0, 0, "", ans);
    return ans;
  }
private:
  void helper(int maxn, int lnum, int rnum, string cur_str, vector<string>& ans) {
    if (cur_str.size() == 2 * maxn) {
      ans.push_back(cur_str);
      return;
    }
    if (lnum < maxn) {
      helper(maxn, lnum+1, rnum, cur_str + "(", ans);
    }
    if (rnum < lnum) {
      helper(maxn, lnum, rnum+1, cur_str + ")", ans);
    }
  }
};