こんにちは
今回の学びは
・入力にに対して文字列だったら重複はありえるか？とか柔軟に考えよう
・略して「条件把握が、解は徐々に」！
・あやしい実行分はマーカーで色塗っとけ！
・ゆえに、少し考えQueueを導入するアイデアにいたりました
・使いまわせそうなfunctionやclassは30秒でかけるように反復しておけ
問題で久々のhard問題です
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
Tの文字列が全部でてくるときの、最小のwindowをさがしてください
後付ですが、この時点で例題はT= "ABC"とあります
しかし、用心深いひとは、T= "AABC"って有り？つまり重複はありか？と聞きます。
私はこれが完全に抜けており途中ででこれを修正するコードに10分ほど費やしております。
ということで早速学びにはいるのは
入力にに対してサンプル以外のパターンも柔軟に考えましょう
たとえば文字列だったら重複はありえるか？空文字はあり得るか？最長文字数の上限はあるか？なのです
こういう、ツッコミは面接官には好印象だとおもいます。
しかしながら若干諸刃の剣的なところがあり、条件が問題を複雑にする場合、いきなり複雑な問題で正解を出しに行こうとすると
逆に時間がかかってしまうことがよくあります。
ですので、
入出力の条件は最初に明らかにするべきですが、問題を解くステップとしては、条件抜きであるいは緩和して段階的に考えるという
テクニック（術）をこころがけましょう
名付けて！ 条件はすべて把握した上で、問題は簡単にしてから段階的に！
略して「条件把握が、解は徐々に」！
初期の段階でhashテーブルを使うというアイデアが浮かびました
そしてサンプルケースで頭と紙でシミュレーションして通ったので
実装しました。
class Solution_works_only_non_duplicated_input: """ # 重複にも対応しないといけない 2108pm # ここはこれまでのでーた構造dict(int)では無理になって # dict(queue)に変更しないといけなくなったので実装にも時間が # かかるかもしれない。デグレもある。 # まさにhardにふさわしい問題だとおもう 2115pm ("aaa", "aa", ""), """ def minWindow(self, S: str, T: str) -> str: if len(S) < len(T): return "" memo = [-1] * len(T) mini = sys.maxsize maxi = -sys.maxsize ans = S index_helper = defaultdict(lambda:-1) for i, c in enumerate(T): index_helper[c] = i counter = 0 for i, c in enumerate(S): idx = index_helper[c] if idx == -1: continue # T以外のキャラ local = max(i, memo[idx]) if memo[idx] == -1: counter+=1 # 初めて見つかったということで。 memo[idx] = max(memo[idx], local) # mini = min(mini, local) # maxi = max(maxi, local) # こっちのが高速だが間違ってるのでまずは。 maxi = max(memo) if counter == len(T): if (maxi+1) - mini < len(ans): ans = S[mini:maxi+1] return ans if counter == len(T) else ""
最初の実装でのポイントはこの問題はO(N)で解けるということが問題にかかれていたので
O(N)で解けなくなるだろうポイント、この場合O(N)のループのなかでさらにO(1)以上のことを
してしまっているポイントで具体的には
mini = min(memo) # O(T)なんんで、これだとO(N)に届かずRTEくらいそう
とい行っているところです。 前もってこのように、長く掛かりそうな行を宣言するのは 後で修正するときに非常に役に立ちます あやしい実行分はマーカーで色塗っとけ！ とい学びです
テストケースをいくつかパスしたところで
大きな壁にぶつかりました。
重複にも対応しないといけないといことです。
これが冒頭でいった
入出力の把握の大事さです
ゆえに、少し考えQueueを導入するアイデアにいたりました
これは素晴らしく、実際最初からつかっていてもよかったほどです。重複じゃないパターンでも。
それに
最初はfrom queue import Queueというpython標準のqueueを利用しようとしましたが
これはqueueがfullになるとqueueが開くまでblockされてしまい、blockしないとfull exceptionがでますし
この挙動を変えるのはclass overrideが必要です。ということで簡易版を自分でつくることにしました。
なければ簡単に作る精神は、エンジニアとしては良い心構えです
面接などの限られた時間のなかでは、たとえば今回作ったQueueなんかでも
ものの一分、あるいは30秒ほどでつくれるように、繰り返し、暗記しておくのも一つのテクニックでしょう
といことで
使いまわせそうなfunctionやclassは30秒でかけるように反復しておけ
今回のclassは簡易queueです
class Queue: def __init__(self, maxsize): self.maxsize = maxsize self.q = [] def add(self, value): self.q.insert(0, value) if len(self.q) > self.maxsize: self.q.pop() def get_last(self): return self.q[-1] def get_min_max(self): return (self.q[0], self.q[-1])
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
最初はO(N*T)で
最終的にはO(N)でおさまりました
。。。
実際の実装はこちら
from collections import defaultdict class Queue: def __init__(self, maxsize): self.maxsize = maxsize self.q = [] def add(self, value): self.q.insert(0, value) if len(self.q) > self.maxsize: self.q.pop() def get_last(self): return self.q[-1] def get_min_max(self): return (self.q[0], self.q[-1]) class Solution: def minWindow(self, S: str, T: str) -> str: if len(S) < len(T): return "" mini = sys.maxsize maxi = -sys.maxsize ans = S index_helper = defaultdict(lambda:-1) for i, c in enumerate(T): index_helper[c] = i # そのキャラは何個かを把握する nums_helper = defaultdict(lambda:0) for i, c in enumerate(T): nums_helper[c] += 1 memo: dict = {} for c, n in nums_helper.items(): q = Queue(n) for _ in range(n): q.add(-1) i = index_helper[c] memo[i] = q counter = 0 for i, c in enumerate(S): idx = index_helper[c] if idx == -1: continue # T以外のキャラ #local = max(i, max(memo[idx].q)) # ってか常にiだとおもう。なので local = i が成立 local = i if memo[idx].get_last() == -1: counter+=1 # 初めて見つかったということで。 memo[idx].add(local) local_mini, local_max = memo[idx].get_min_max() # mini = min(mini, local_mini) # maxi = max(maxi, local_max) # ここでハッと気づく。 # 2156pmデグレった mini = min([q.q[-1] for c, q in memo.items()]) # O(T)からO(1)に改善できたので通りました！ maxi = max([q.q[0] for c, q in memo.items()]) # mini = min([min(q.q) for c, q in memo.items()]) # O(T)なんんで、これだとO(N)に届かずRTEくらいそう # maxi = max([max(q.q) for c, q in memo.items()]) if counter == len(T): if (maxi+1) - mini < len(ans): ans = S[mini:maxi+1] return ans if counter == len(T) else ""
実装後です。timespace analysis (時間とスペースの分析）は O(N)
しかし実行速度は800msと下位5%です
上位15%の彼との違いから学びをあぶりだしませんか？
ひとつはarrayつかってないね。なして、そんなことできる、よーくみて。
まとめ
・入力にに対してサンプル以外のパターンも柔軟に考えましょう
・略して「条件把握が、解は徐々に」！
・あやしい実行分はマーカーで色塗っとけ！
・ゆえに、少し考えQueueを導入するアイデアにいたりました
・使いまわせそうなfunctionやclassは30秒でかけるように反復しておけ
以上です