いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode easy 720 Longest Word in Dictionary

投稿日:

こんにちは

今回の学びは

・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で笑&真剣。

終始、わからないことは声にだして、明確にしていきましょう。

1,まずは入出力をしっかりおさえましょう。(問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと)

 

2,いくつかのソリューションを声にだして出してみましょう。(もちろんtime complexit, space complexityの分析や理由を付け加えて)

 

3,どれでいくか、一緒に決定しましょう。(理由付きでね、よろしく)

timespace analysis (時間とスペースの分析)は 〇〇です

 

場合によっては、pseudocode(擬似コード)をかいてみてもよい。

 

4、実装しましょう。

最初、Trie実装を改修して、1文字だけ新しい文字を登録できたら

と描きたかったのだけどすこし複雑で頭が付いて行ってなかったので56/57ケースとかで

落ちた時に詰まった感があり。その時、
1文字前までの登録があれば、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

うまく行った、1文字前までの登録があれば、insertする、というアイデアが浮かんだ

の実装はこちら

遅いけど通った
Runtime: 492 ms, faster than 5.85% of Python3 online submissions for Longest Word in Dictionary.

 

5、エッジケースとサンプルテストを忘れずに!

 

 

 

振り返り

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

Trieは基本である。基本の関数を使いまわせる方が綺麗な設計。できない場合は設計が悪いを疑う。詰まるというのは大抵、設計が悪い。

 

 

 

 

まとめ

・Trieは基本である。基本の関数を使いまわせる方が綺麗な設計。できない場合は設計が悪いを疑う。詰まるというのは大抵、設計が悪い。

 

以上です

-アルゴリズム
-

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