こんにちは
今回の学びは
・Trieは基本である。基本の関数を使いまわせる方が綺麗な設計。できない場合は設計が悪いを疑う。詰まるというのは大抵、設計が悪い。
問題はlongest-word-in-dictionary なおこの問題はeasyとありますが、mediumの【アルゴリズム脳トレ】leetcode medium 208 Implement Trie (Prefix Tree) の発展系で実質easyは妥当なレベルではなくmediumだと思う
（時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装 20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）
３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）
timespace analysis (時間とスペースの分析）は 〇〇です
場合によっては、pseudocode（擬似コード）をかいてみてもよい。
４、実装しましょう。
最初、Trie実装を改修して、１文字だけ新しい文字を登録できたら
と描きたかったのだけどすこし複雑で頭が付いて行ってなかったので56/57ケースとかで
落ちた時に詰まった感があり。その時、
１文字前までの登録があれば、insertする、というアイデアが浮かんだ
最初の行き詰まった実装はこちらで
class Trie:
def __init__(self):
self.db = {}
def insert(self, word: str) -> None:
curr = self.db
total_n_new_chars = 0
for i, c in enumerate(word):
if c in curr:
if i == len(word) - 1: curr[c].update({"end":{}})
else: curr[c].update({})
else:
if i == len(word) - 1:
curr[c] = {"end":{}}
return True
else:
curr[c] = {}
return False
curr = curr[c]
return True
class Solution:
def longestWord(self, words: List[str]) -> str:
sorted_words = sorted(words)
trie = Trie()
import bisect
A = []
maxi = -sys.maxsize
for word in sorted_words:
if trie.insert(word):
if len(word) > maxi:
A = [] # reset
maxi = len(word)
bisect.insort_left(A, word)
A = [chars for chars in A if len(chars) == maxi]
#print(A, maxi)
return A[0] if len(A) > 0 else None
うまく行った、１文字前までの登録があれば、insertする、というアイデアが浮かんだ
の実装はこちら
遅いけど通った
Runtime: 492 ms, faster than 5.85% of Python3 online submissions for Longest Word in Dictionary.
５、エッジケースとサンプルテストを忘れずに！
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
Trieは基本である。基本の関数を使いまわせる方が綺麗な設計。できない場合は設計が悪いを疑う。詰まるというのは大抵、設計が悪い。
まとめ
・Trieは基本である。基本の関数を使いまわせる方が綺麗な設計。できない場合は設計が悪いを疑う。詰まるというのは大抵、設計が悪い。
以上です