こんにちは
今回の学びは
・ソートされた配列と二分木はよく似てるよ。
・できれば二分木探索を配列で実装していて 🙂
問題は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をつかえるよ。
まとめ
以上です