アルゴリズム

leetcode medium generate parentheses

投稿日：

こんにちは

・O(n**2)でも枝刈りでクリア可能

・デバッグはめんどくさくても手書きが結局早い

・枝刈りの条件をしっかりと意識して、それが崩れないようにする　という意識

今回の学びは

 

問題は

3と言われたらカッコ（）をみっつ使って作れる有効なカッコの組み合わせをつくって　という問題

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

なんとなく再帰かなーと

思わせますね。初見

１つだったら()

２つだったら()(), (())

３つだったら()()(), (()()), (())(), ()(()), ((()))

となって、イメージ的にこんなことができないですかね。

def rec()
  if n == 1: 
    return ()
  else:
    patterns =  rec(n-1)
    ( + patterns + )
    patterns + ()
    () + patterns

 

実装前後でこれは毎回書きましょう。timespace anaylysis (時間とスペースの分析）は　O(n)でスペースはstackでO(n)となります

 

分析では

十分なアルゴリズムなので実装します

実際の実装はこちら

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        return list(filter(lambda x : len(x) == n*2, self.rec(n)))
        #return self.rec(n)

    def rec(self, n: int) -> List[str]:
        if n == 0:
            return []
        elif n == 1:
            return ["()"]
        else:
            patterns = self.rec(n-1)
            combs = set(patterns)
            for pattern in patterns:
                combs.add("()" + pattern)
                combs.add("(" + pattern + ")")
                combs.add(pattern + "()")
            patterns2 = self.rec(n-2)
            for pattern in patterns2:
                for patternX in self.rec(2):
                    combs.add(pattern + patternX)

            return list(combs)


print(Solution().generateParenthesis(1))
print(Solution().generateParenthesis(2))
print(Solution().generateParenthesis(3))
print(Solution().generateParenthesis(4))

最初はpatterns2もない状態でしたがそうそうにrec(4)でだめでしたので

patterns2を追加したのですが今度はrec(5)でえらーになりました

ちょっと考え直して以下のように修正しましたがこちらも意図通りではなく

不正な）からスタートする文字列が表示されます。。。これのデバッグができません。。。苦戦

['))((', '(())', ')(()', ')()(', '()()']

とう結果に。以下のコードです

class Solution:
    def rec(self, chosen, o: int, c: int) -> List[str]:
        print("chosen:%s, o:%d, c:%d" % (chosen, o, c))
        if o < 0 or c < 0:
            print("no good! = self.rec(%s, %s, %s)" % (chosen, o, c))
            return []
        elif c < o:
            print("no good2 = self.rec(%s, %s, %s)" % (chosen, o, c))
            return []
        elif c == 0:
            print("Valid!!:%s" % chosen)
            return [chosen]
        else:
            combs = []
            combs += self.rec('(' + chosen, o-1, c)
            combs += self.rec(chosen + '(', o-1, c)
            combs += self.rec(chosen + ')', o, c-1)
            combs += self.rec(')' + chosen, o, c-1)
            return list(set(combs))


    def generateParenthesis(self, n: int) -> List[str]:
        return self.rec("", n, n)


# print(Solution().generateParenthesis(1))
print(Solution().generateParenthesis(2))

これのデバッグは

手書きで、めんどくさいですが書いてみることで判明しました。

めんどくさいとおもいますが、多少長い再帰でも実際に書いてみることが近道です　

コードを眺めて、頭の中で実行していたときには、）でスタートしたケースはかながらずreturn []で終了するので

なぜ最終的に不正なカッコの組み合わせがかえされるのか理解できませんでしたが

書いてみたら一目瞭然、最後の最後でo = 0, c =0 隣りつつも ')' + chosenとなれるので（頭の中の想像とは違うという意味で）意図せぬ

結果となっていたようです。

さあ　修正していきましょう

違いはここだけ  先頭に付け足すのをやめました

combs = []
combs += self.rec(chosen + '(', o-1, c)
combs += self.rec(chosen + ')', o, c-1)
return list(set(combs))

全体はこのように

class Solution:
    def rec(self, chosen, o: int, c: int) -> List[str]:
        if o < 0 or c < 0:
            return []
        elif c < o:
            return []
        elif c == 0:
            return [chosen]
        else:
            combs = []
            combs += self.rec(chosen + '(', o-1, c)
            combs += self.rec(chosen + ')', o, c-1)
            return list(set(combs))

    def generateParenthesis(self, n: int) -> List[str]:
        return self.rec("", n, n)

 

 

実装後です。timespace anaylysis (時間とスペースの分析）は　O(n**2) - backtrackingとうところでしょう　スペースは　O(n**2)でスタックスペースになります

やっときた♪

 

ちなみに昔の回答のほうがスッキリしている

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def backtrack(S, left, right):
            if len(S) == 2*n:
                res.append(S)
                return

            if left < n:
                backtrack(S + '(', left + 1, right)
            if left > right:
                backtrack(S + ')', left, right + 1)
        backtrack("", 0, 0)
        return res

 

おそらくなんかの答えをみてしまったのだと

思うのですが、言いたいのは数週間前に取り組んだ問題が

解けない、もしくはハマった（デバグに時間かかりすぎ）というのは

反省点が多いといえる

一回勉強したときに、納得いくまで理解できていないとうこと

応用できるための、その問題の根幹というか秘孔というか中心というか

肝というか

そういったものを掴まずにただただ問題をこなしているという点がまずいと思うのですが

それらを記していくことが

近道だとおもっています。

さて

肝はなんでしょうか？それはo(n**2)の２値で回答が膨張していく解法ですが

うまく枝刈りができるかとうことです。

幸い、枝刈りはすぐに、思い付いた。数週間前にやったことは無駄ではなかったですね。

そこから再帰の呼び出しに必要なケースが間違っていた

選んだもの先頭にに）クローズのカッコを挿入するということが枝刈りのための条件を完全無視する

という事実に着眼できていない

つまりは枝刈りの重要性、意味が曖昧なままとりくんでいたので

枝刈りの条件をしっかりと意識して、それが崩れないようにする　という意識が

必要なんだとおもいました。

 

まとめ

・O(n**2)でも枝刈りでクリア可能

・デバッグはめんどくさくても手書きが結局早い

・枝刈りの条件をしっかりと意識して、それが崩れないようにする　という意識

以上です

-アルゴリズム

Copyright© CTOを目指す日記 , 2024 All Rights Reserved.