いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode easy 20 valid parentheses

投稿日:

こんにちは

今回の学びは

最初に入出力をしっかり把握するという鉄則

・ドハマリしたら何かが根本的に悪い。答えはいつももっとシンプル

 

問題は。。。

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

まずは入出力をしっかりおさえましょう。

 

八ヶ月前は難しくてできなかったeasy問題が

簡単に一発でとけるようにあった。

なにがかわったか。

 

とりあえず、

今回のアイデアとしてはstackを使うという点。

これでO(N)でとけそう

 

空文字はTrueとするという問題分をみた瞬間

class Solution:
    def isValid(self, s: str) -> bool:
        if s == "": return True

と書いてしまうと、ひとつ小さな問題がとけって

後々引っ張らずにスッキリする。小さい問題ならその場ですぐ片付けてしまえ。

 

 

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析)は 

 

 

実際の実装はこちら

class Solution:
    def isValid(self, s: str) -> bool:
        if s == "": return True
        OPEN = ['(', '[', '{'] # ideally use char code
        stack = []
        for c in s:
            if c in OPEN:
                stack.append(c)
            else:
                if len(stack) == 0: return False
                o = stack.pop()
                if o == '(' and c == ')': pass
                elif o == '[' and c == ']': pass
                elif o == '{' and c == '}': pass
                else: return False
        # through to end and no stack left => True
        return len(stack) == 0

 

実装後です。timespace analysis (時間とスペースの分析)は O(N)に多少O(3)のルックアップがはいっていますね

コード内コメントにも書いていますが理想的にはascii codeを利用してintの比較でもっていけそう

 

それにしても

八ヶ月前は、こんな状態だったのですが

初期のころの実装をみながら、どこがどう成長したのか、見れたらなとおもいます。

そこからあらたな発見があれば嬉しいのですが。では

一番最初、再帰的にかんがえていますね。

いや、筋はわるくないですよ。以下最初の提出のコード

とおもいきや。

[0:2]とかのマジックナンバー使っているところはセンスがないです

class Solution:
    def validate(self, s):
        if len(s) == 2:
            if s == "()" or s == "{}" or s == "[]": return True
        else: return False
        
    def rec(self, s):
        if self.validate(s[0:2]):
            s = s[2:]
        if len(s) == 0:
            return True
        if len(s) == 2:
            return self.validate(s)
        elif len(s) > 2 and len(s) % 2 == 0:
            return self.validate(s[0]+s[-1]) and self.rec(s[1:-1])
        else:
            return False
            
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        return self.rec(s)

しかし

これでドハマリしている様子

一番悪いのは、このアルゴリズム{}()[]とか常にセットでくることを想定していて

((()))みたいなパターンに対応できていない!

これは最初に入出力をしっかり把握するという鉄則

に反しており、故にハマって焦って、というドツボにおちたとかんがえられる

 

逆にstackを使おうみたいな発想はどっからくるんだろー

わたしの今回の場合は、もう過去の経験もあり括弧問題 = スタックつかそう

くらいにパターン化されていので、スッと今回解けた要因もあるとおもう。

もどって

どうやったらstackという発想をえられただろうか?

 

まぁ一個は対さがしゲームみたいなものだから

対がみつかるまで、一方を保存しておく必要がある、とう点

それだけなら、ハッシュでも配列でも良さそうだけど

対が見つかればもうその対は捨てても問題ない、という問題上の性質からstackが使いやすそう!

とう思考経路だろうか。

 

ここまでいろんな問題やってきて

初期のようにこれだけハマっている場合って

もっと簡単にとける方法があるはずで、一旦振り出しに戻るべきなんだようなー

それができるように

なるっということは成長しているってことで。

さらに

入出力をしっかり抑えてから走り出すことができるよに

なれば

もっと成長しているといこと

アルゴリズムの脳筋肉がついてきたということ

 

まとめ

最初に入出力をしっかり把握するという鉄則

・ドハマリしたら何かが根本的に悪い。答えはいつももっとシンプル

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.