820. Short Encoding of Words

A valid encoding of an array of words is any reference string s and array of indices indices such that: words.length == indices.length.

The reference string s ends with the '#' character. For each index indices[i], the substring of s starting from indices[i] and up to (but not including) the next '#' character is equal to words[i]. Given an array of words, return the length of the shortest reference string s possible of any valid encoding of words.

The way the Trie data structure is written is awesome

def minimumLengthEncoding(self, words):
    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)