こんにちは
今回の学びは
・状態変数が多いならば、データ構造をつかってより楽にできないか？自問すること。
・文字の登場順と回数を問おているのでhashpmapが最適です
問題はexpressive-words mediumです
この問題はどうやらgoogleの電話面接でも聞かれたことがあるようです
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
アイデアは
伸びた数を数えて、違反していないか確認していく方法。
途中、開始以前から同じ文字の場合のカウントをしていなくてk=iでマイナス方向への
whileループを導入した
しかし28/29目のテストケースで落ち、
このスパゲッティソースを管理したくない、タイムアップとうことで
断念した。これまでに45分という時間を使っていた。ちなみに最初の提出までは20分だった。
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
len(words)をMとすると
O(N*M)で十分とみた。しかしマイナス方向へのwhileがあるのだが、これもmaxiumで2NにしかならないのでOK。DPも考えたがDPはO(N*len(word)*M)なのでもっと掛かるのでだめ。
実際の実装はこちら
class Solution:
def expressiveWords(self, S: str, words: List[str]) -> int:
#print(S, words)
def is_stretchy(S, word):
i = j = 0
if S[i] != word[j]: return False
if len(S) <= len(word)+1: return False
i = j = 1
while not(i == len(S) and j == len(word)):
if j >= len(word): j = len(word) - 1
if i >= len(S): i = len(S) - 1
if S[i] == word[j]:
i += 1
j += 1
else:
if S[i-1] == S[i]:
stretchy_cnt = 1
k = i
while S[k-2] == S[i] and k >= 0:
k -= 1
stretchy_cnt += 1
while S[i-1] == S[i]:
stretchy_cnt += 1
i += 1
if stretchy_cnt < 3:
return False
else:
return False
return True
counter = 0
for word in words:
if is_stretchy(S, word):
counter += 1
return counter
悪くはないが、
デバックしにくい。すでに実装者が混乱している。
28/29のテストケースで落ち、もはやデバッグする気が失せる入力である。
つくりなおしたほうが速いわ！というレベル勘をもって。
discussionを見ると、やはりもっといい回答がたくさんある。
こちら、単純なhashmapで数え上げるプログラム。気に入った。
"""
heeellooo
hello
まずはsの登場文字順にrepeat数をかぞえましょう
(h:1, e:3, l:2, o:3)
(h:1, e:1, l:2, o:1)
配列の長さも当然おなじ
文字が全部同じであること。
上のほうが、長さが3以上あること。
下の文字のほうが、常に小さい
"""
実装後です。timespace analysis (時間とスペースの分析）は O(N*M)
ということで
実装は
class Solution:
def expressiveWords(self, S: str, words: List[str]) -> int:
def c_count(S):
if S is None or len(S) == 0: return []
cc = []
moji = S[0]
moji_idx = 0
for i in range(len(S)+1):
if i < len(S) and S[i] == moji:
pass
else:
cc.append((moji, i - moji_idx))
if i < len(S):
moji = S[i]
moji_idx = i
return cc
def is_stretcy(cc1, cc2):
# cc1 = c_count(S)
# cc2 = c_count(T)
# cc is list of tuple('c': int)
# print(cc1)
# print(cc2)
if len(cc1) != len(cc2): return False
for i in range(len(cc1)):
if cc1[i][0] != cc2[i][0]: return False
if cc1[i][1] != cc2[i][1] and cc1[i][1] < 3: return False
if cc1[i][1] < cc2[i][1]: return False
return True
counter = 0
cc1 = c_count(S)
for T in words:
cc2 = c_count(T)
if is_stretcy(cc1, cc2):
counter += 1
return counter
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
文字の現れる順番は必ず同じだからhashmapでなんとかしましょう。
ちょっと詳細。
私は最初、この問題をポインターをつかって解こうとしてハマった。うまいひとならこれでも
すんなり実装できるはず。状態はS, Tのポインター、最初マッチのindex, 文字がずれたときの文字数など、結構管理が大変だった。ならば、他にもっと少ない変数で解けないか？使えるデータ構造はないか？と考えて欲しい。
状態変数が多いならば、データ構造をつかってより楽にできないか？自問すること。
文字の登場順と回数を問おているのでhashpmapが最適です
「この問題にタグをつけるなら？」
hashmap
まとめ
・状態変数が多いならば、データ構造をつかってより楽にできないか？自問すること。
・文字の登場順と回数を問おているのでhashpmapが最適です
以上です