820.-short-encoding-of-words.md

820. Short Encoding of Words

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        words = list(set(words)) #需要去重，否则在之后计算“叶子高度”的时候会重复计算
        trie={} #这是字典树的根
        nodes=[] #这里保存着每个word对应的最后一个节点，比如对于单词time，它保存字母t对应的节点（因为是从后往前找的）
        for word in words:
            now=trie
            for w in reversed(word):
                if w in now:
                    now=now[w]
                else:
                    now[w]={}
                    now=now[w]
            nodes.append(now)
       ## Python 递归 
        Trie = lambda: collections.defaultdict(Trie)
        trie = Trie()
        for word in words:
            now=trie
            for w in word[::-1]:
                now=now[w]
            nodes.append(now)    
            
            
        
        ans=0
        for w,c in zip(words,nodes):
            if len(c)==0: #一个空字典，意味着这个节点是个叶子
                ans+=len(w)+1
        return ans