単語の圧縮符号化

820.単語の圧縮符号化

単語リストが与えられ、このリストは、インデックス文字列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] 。

# ， 
def minimumLengthEncoding(words):
    if not words:
        return ""
    vocab = set(words)
    for word in words:
        # 
        for i in range(1,len(word)):
            vocab.discard(word[i:])

    length = sum(len(w) for w in vocab)+len(vocab)
    return length

# ， ， 
class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        if not words:
            return 0
        root = {}
        is_end = -1
        length = 0
        # 
        words.sort(key=lambda x:len(x),reverse=True)
        
        for word in words:
            curNode = root
            is_new = 0  
            for char in word[::-1]:# ， 
                if char not in curNode:# ， ， 
                    is_new = 1  # 
                    curNode[char] = {}
                curNode = curNode[char]
            curNode[is_end] = True  # 
            length += len(word)+1 if is_new else 0  # +， 
        return length