毎日1題、毎日1練習.13単語の圧縮符号化(辞書ツリーは何ですか?役に立つ知識が増えました!)

単語の圧縮符号化所与の単語リストを、インデックス文字列SとインデックスリストAとに符号化する.

たとえば、このリストが["time","me","bell"]の場合、S="time#bell#",indexes=[0,2,5]と表すことができます.
各インデックスについては、文字列S内のインデックスの位置から文字列の読み取りを開始し、「#」が終了するまで、前の単語リストを復元できます.では、与えられた単語リストを符号化することに成功した最小文字列の長さはどのくらいですか.
例:
入力:words=["time","me","bell"]出力:10説明:S="time#bell#",indexes=[0,2,5].
ヒント:
1 <= words.length <= 2000 1 <= words[i].length<=7各単語は小文字です.
この問題の基本的な考え方は、もし1つの単語が別の単語の接尾辞であれば、私たちの2つの単語は1つの「#」の終端子を共用しているが、最初のインデックスの位置が異なるだけで、私たちは1つのwordの集合を創造して、集合の中のすべての単語に対して、私たちは集合の中で彼らのすべての接尾辞を削除します(この接尾辞は追加の符号化を必要としないため)、そして集合が残っている語は、「#」で追加符号化し、合計の長さと数を返す必要があります(各語には「#」)
コードは次のとおりです.

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        a=set(words)
        co=0
        for i in words:
            for c in range(1,len(i)):
                a.discard(i[c:])
        co=len(a)
        for d in a:
            co=co+len(d)
        return co

本編に入り、辞書ツリー
辞書ツリーのアーキテクチャとツリーのアーキテクチャはこのように対応しています.
ノード:パス上のアルファベットからなる単語パス:アルファベット
ルートノードは空です.はい、ルートノードには単語を構成するパスがないので、最初のアルファベットが異なり、最初のパスも異なります.パスに沿って下りて、パスアルファベットを収集します.私たちは各リーフノードで最終的に欲しい単語をつづり、このパスが分岐したときに、前の同じノードを記録します.単語には共通接頭辞が反映されていますが、私たちのこの問題には共通接尾辞が必要なので、逆に単語を記録します.後から前へ、新しい葉が現れない経路があれば(前の経路に沿ってこの単語を収集することができます)、共通接尾辞があると認識されます.つまり、すべての単語が木に入ると、すべての葉の結点の単語に必要な長さが含まれます.残りの単語は葉の結点に達していないうちに木のあるノード(つまり共通接尾辞の場合)に存在するので、公式の問題解を持ってきました.

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        words = list(set(words)) #remove duplicates
        #Trie is a nested dictionary with nodes created
        # when fetched entries are missing
        Trie = lambda: collections.defaultdict(Trie)
        trie = Trie()# 

        #reduce(..., S, trie) is trie[S[0]][S[1]][S[2]][...][S[S.length - 1]]
        nodes = [reduce(dict.__getitem__, word[::-1], trie)
                 for word in words]# 

        #Add word to the answer if it's node has no neighbors
        return sum(len(word) + 1
                   for i, word in enumerate(words)
                   if len(nodes[i]) == 0)# +“#”
              

役に立つ知識が増えました!!