ゼロから始めるLeetCode Day55「22. Generate Parentheses」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day54 「1290. Convert Binary Number in a Linked List to Integer」
次回
ゼロから始めるLeetCode Day56 「1480. Running Sum of 1d Array」

Twitterやってます。

#問題
22. Generate Parentheses

難易度はMedium。
Top 100 Liked Questionsからの抜粋です。

問題としては、正の整数であるnが与えられます。その数の括弧の組み合わせを全て書き出すようなアルゴリズムを設計しましょう、というものです。

最近知ったんですけど自然数って大学数学とかだと0も含むんですね・・・

For example, given n = 3, a solution set is:
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

例を見た方が分かりやすいですね。

# 解法

組み合わせについての問題です、今回初見で解けなかったのでdiscussをチラチラ見て考え方を勉強して書きました。

カッコを右、`right`と左、`left`に分けて考えると分かりやすいです。
それぞれの引数として`n`を当てて、それらが0になるまで追加を続ける、といういわゆるバックトラック法的な考え方をすれば比較的すんなり解けると思います。

具体的な条件付けとしては

- 括弧の最初と最後の配置は絶対であること
- 両方が0になったら配列に追加すること
- それ以外の場合は再帰的に関数を呼び返すということ

以下のコードでは`dfs`を別にまとめて見やすくしています。


```Python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        self.dfs(n,n,"",ans)
        return ans
    
    def dfs(self,left,right,path,ans):
        if left > right or left < 0 or right < 0:
            return 
        if left == 0 and right == 0:
            ans.append(path)
            return
        self.dfs(left-1,right,path+'(',ans)
        self.dfs(left,right-1,path+')',ans)
# Runtime: 32 ms, faster than 78.59% of Python3 online submissions for Generate Parentheses.
# Memory Usage: 13.9 MB, less than 93.80% of Python3 online submissions for Generate Parentheses.

最近気付いたのですが、LeetCodeはEasyからMediumに変わると扱う変数が増えたり、プログラミング言語に詳しいというよりは数学の確率や場合の数、整数的な知識があると解きやすくなるという印象を受けました。

これらのインタビューを受けるような人の多くは情報系や理系のことが多く、そういった知識も苦にしなさそうな感じがありますが、私のように数弱マンだと問題を見た時にん？となることが多いので、これ以上の難易度に挑む上でそういった知識も付けていく必要がありそうですね。

では今回はここまで。
お疲れ様でした。