820. Short Encoding of Words

https://leetcode.com/problems/short-encoding-of-words/

Python

Reversed words in Trie

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        words = set(words)

        trie = dict()
        for word in words:
            cur = trie
            for char in word[::-1]:
                cur = cur.setdefault(char, dict())

        ans = 0
        for word in words:
            node = trie
            for char in word[::-1]:
                if char in node:
                    node = node[char]
                    continue
                break

            # node is leaf, which present the prefix without overlap
            if len(node) == 0:
                ans += len(word)+1
        return ans