こんにちは
今回の学びは
・最初に入出力をしっかり把握するという鉄則
・ドハマリしたら何かが根本的に悪い。答えはいつももっとシンプル
問題は。。。
（時間配分は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が使いやすそう！
とう思考経路だろうか。
ここまでいろんな問題やってきて
初期のようにこれだけハマっている場合って
もっと簡単にとける方法があるはずで、一旦振り出しに戻るべきなんだようなー
それができるように
なるっということは成長しているってことで。
さらに
入出力をしっかり抑えてから走り出すことができるよに
なれば
もっと成長しているといこと
アルゴリズムの脳筋肉がついてきたということ
まとめ
・最初に入出力をしっかり把握するという鉄則
・ドハマリしたら何かが根本的に悪い。答えはいつももっとシンプル
以上です