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

If we look carefully we can notice that we need to write all words such that they are not suffix of some other word. We can do it just in bruteforce way, for each word checking if suffix of this word alredy here or not.

However as usual, when the problem is about suffixes or prefixes of words it is good idea to think about tries. Notice, that if we reverse words and put them into trie, than for ["time", "me", "bell"], we will put emit, em, lleb, so if one word was suffix of another, now it is is prefix, and this is what tries are about.

In addition to classical trie data structure we want to keep list ends, so we can have quick access to them (usual way is for every node have IsEnd field which is true if some word ends with this node, but in this case we need to traverse all tree second time). Finally, we iterate over all ends and check that we can not continue this word, that is it is leaf of tree.

Complexity: time complexity is O(w_1 + ... + w_n), where w_i is length of i-th word: we need to traverse each word and put it to trie and then traverse all n end points. Space complexity is also O(w_1 + ... + w_n).

class TrieNode:
    def __init__(self):
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()
        self.ends = []

    def insert(self, word): #None
        root = self.root
        for symbol in word:
            root = root.children.setdefault(symbol, TrieNode())
        self.ends.append((root, len(word) + 1))

class Solution:
    def minimumLengthEncoding(self, words):
        trie, ans = Trie(), 0
        
        for word in set(words):
            trie.insert(word[::-1])
        
        return sum(depth for node, depth in trie.ends if len(node.children) == 0)

Remark Even though complexity here is O(w_1 + ... + w_n) and straightforward algorithm it is O(w_1^2 + ... + w_n^2), here it can work slower, because lengths of words are very small and working with strings is faster than working with complex trie data structure we created here.

If you like the solution, you can upvote it on leetcode discussion section: Problem 0820