いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode hard 76 minimum window substring

投稿日:

こんにちは

今回の学びは

・入力にに対して文字列だったら重複はありえるか?とか柔軟に考えよう

略して「条件把握が、解は徐々に」!

・あやしい実行分はマーカーで色塗っとけ!

・ゆえに、少し考え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%の彼との違いから学びをあぶりだしませんか?

https://leetcode.com/problems/minimum-window-substring/discuss/382853/Python-87-time-solution-heavily-commented

ひとつはarrayつかってないね。なして、そんなことできる、よーくみて。

 

 

まとめ

・入力にに対してサンプル以外のパターンも柔軟に考えましょう

略して「条件把握が、解は徐々に」!

・あやしい実行分はマーカーで色塗っとけ!

・ゆえに、少し考えQueueを導入するアイデアにいたりました

・使いまわせそうなfunctionやclassは30秒でかけるように反復しておけ

以上です

-アルゴリズム

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