いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 3 longest substring without repeating characters

投稿日:

こんにちは

今回の学びは

・ソートされた配列と二分木はよく似てるよ。

・できれば二分木探索を配列で実装していて 🙂

問題はlongest-substring-without-repeating-characters

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

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

 

この問題は後に勉強してわかったことなのですが

sliding windowのテンプレートがうまく使えます。

もうすこしちゃんというとhmapを利用した条件判定とsliding windowの組み合わせた技です。

まずは、

この知識がなかった時にどのように解いたか見てみましょう。

sofarとうマップにindexを保持させて、条件が外れた時に(条件が外れた時とは、この場合、重複が起きてしまっと時)

そこまで戻って操作を繰り返すやりかたで、中々秀逸である。

悪くない。ただこの回答にこぎつくまでの時間はながかったと記憶している。

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        import sys
        from collections import defaultdict
        sofar = {}
        i = 0
        maxi = tmp = 0
        while True:
            if i == len(s): break
            cur = s[i]
            if cur not in sofar.keys():
                # まだ
                sofar[cur] = i
                tmp +=1
                maxi = max(tmp, maxi)
                i+=1
            else:
                # あかん、リセット
                next_i = sofar[cur] + 1
                tmp = 0
                sofar = {}
                i = next_i
        return maxi

 

途中、こういう解き方もしている。

しかし、再現性がすくない。というのも数週間後、読み返すと読みづらい。。何を書いているの

難しい。メンテしずらい。。。

そのコードはこれ。アイデアはいいが変数名とか、ちょっとロジックごっちゃっていて読みにくいと感じた。

from collections import defaultdict
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # remember last index
        # if same char, curr - last index.
        # update the maxi all the time
        # O(n) algorithm
        memo = defaultdict(lambda : -1)
        maxi = 0
        j = -1
        for i, c in enumerate(s):
            if memo[c] >= 0: # already exist
                if j > memo[c]:
                    cur = i - j + 1
                else:
                    cur = i - memo[c]
                maxi = max(maxi, cur)
                j = max(j, memo[c] + 1)
            else:
                extra = 1 if j >= 0 and s[j] != s[i] else 0
                maxi = max(maxi, i-j+extra)
            memo[c] = i
        return maxi

 

 

その後も何度かこの問題とは対峙してきたようだ。

久しぶりに解いて

一瞬で解けたから、成長したかなーと実感した。

class Solution:
    def lengthOfLongestSubstring(self, S: str) -> int:
        if S is None or len(S) == 0: return 0
        sz = len(S)
        l = 0
        r = 1
        maxi = 1
        while l < sz and r < sz:
            print("l -> %s, r -> %s" % (l, r))
            if S[r] in S[l:r]:
                # move l until  non overlap point
                while S[l] != S[r]:
                    l += 1
                l += 1
            else:
                maxi = max(maxi, r - l + 1)
                # move r +1
                r += 1


        return maxi

tO(N^2)がかかっていると思います。この s[r] in S[l:r]はコスティだと思う。

まぁ、実際はスコアとスピードは早かった。

 

しかし、次の問題(substring with concatination of all words)で玉砕されたのだけどw

という

ながれでsliding templateを勉強したんですが、

実際、それを

利用して、テンプレートを利用しても解いています。

from collections import defaultdict
class Solution:
    def lengthOfLongestSubstring(self, S: str) -> int:
        maxi: int = 0
        hmap: DefaultDict[str, int] = defaultdict(int)
        counter = len(hmap)
        l = r = 0 # sliding window pointers

        while r < len(S):
            #print("l:%s, r:%s, counter:%s, hmap:%s" % (l, r, counter, hmap))
            c = S[r]

            hmap[c] += 1
            if hmap[c] > 1:
                counter += 1 # 違反
            r += 1

            # l(left) pointerと管理変数をクリアするロジック
            while counter > 0: # depends on condition
                #--- business logic ---
                cl = S[l] # c(character) at left pointer
                hmap[cl] -= 1
                if cl == c and hmap[cl] < 2:
                    counter -= 1 # break
                l += 1

            # save or update the result if find T
            maxi = max(maxi, r - l)
        return maxi

 

実装後です。timespace analysis (時間とスペースの分析)は ◯◯

 

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

スライディングtemplateをつかえるよ。

 

まとめ

 

以上です

-アルゴリズム

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