# 820. Short Encoding of Words¶

## Approach 1: Trie¶

• Time: $O(\Sigma \texttt{words[i]})$
• Space: $O(\Sigma \texttt{words[i]})$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 struct TrieNode { vector> children; int depth = 0; TrieNode() : children(26) {} }; class Solution { public: int minimumLengthEncoding(vector& words) { int ans = 0; shared_ptr root = make_shared(); vector> heads; for (const string& word : unordered_set(words.begin(), words.end())) heads.push_back(insert(root, word)); for (shared_ptr head : heads) if (ranges::all_of(head->children, [](const auto& child) { return child == nullptr; })) ans += head->depth + 1; return ans; } private: shared_ptr insert(shared_ptr root, const string& word) { shared_ptr node = root; for (const char c : string(word.rbegin(), word.rend())) { const int i = c - 'a'; if (node->children[i] == nullptr) node->children[i] = make_shared(); node = node->children[i]; } node->depth = word.length(); return node; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class TrieNode { public TrieNode[] children = new TrieNode[26]; public int depth = 0; } class Solution { public int minimumLengthEncoding(String[] words) { int ans = 0; TrieNode root = new TrieNode(); List heads = new ArrayList<>(); for (final String word : new HashSet<>(Arrays.asList(words))) heads.add(insert(root, word)); for (TrieNode head : heads) if (Arrays.stream(head.children).allMatch(child -> child == null)) ans += head.depth + 1; return ans; } private TrieNode insert(TrieNode root, final String word) { TrieNode node = root; for (final char c : new StringBuilder(word).reverse().toString().toCharArray()) { final int i = c - 'a'; if (node.children[i] == null) node.children[i] = new TrieNode(); node = node.children[i]; } node.depth = word.length(); return node; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class TrieNode: def __init__(self): self.children: Dict[str, TrieNode] = {} self.depth = 0 class Solution: def minimumLengthEncoding(self, words: List[str]) -> int: root = TrieNode() leaves = [] def insert(word: str) -> TrieNode: node = root for c in reversed(word): node = node.children.setdefault(c, TrieNode()) node.depth = len(word) return node for word in set(words): leaves.append(insert(word)) return sum(leaf.depth + 1 for leaf in leaves if not len(leaf.children)) 

## Approach 2: C++ string_view¶

• Time: $O(|\texttt{words}| \cdot |\texttt{words[i]}|^2)$
• Space: $O(|\texttt{words}| \cdot |\texttt{words[i]}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: int minimumLengthEncoding(vector& words) { unordered_set wordsSet(words.begin(), words.end()); for (const string& word : words) { const string_view sv(word); for (int i = 1; i < word.length(); ++i) wordsSet.erase(sv.substr(i)); } return accumulate(wordsSet.begin(), wordsSet.end(), 0, [](int subtotal, const auto& sv) { return subtotal + sv.length() + 1; }); } };