题目地址：

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

给定一个英文小写字母的单词列表AAA，要求构造一个最短的字符串sss作为该列表的一种编码，编码方式为：
1、sss以'#'结尾；
2、解码结果搭配一个非负整数数组BBB，BBB与AAA长度相等，并且从s[B[i]]s[B[i]]s[B[i]]开始向后直到最近的'#'之间的子串即为A[i]A[i]A[i]。
求sss的长度。

可以用Trie。如果某两个个串，其中一个是另一个的后缀，显然可以用那个最长的来避免编码的重复。我们在AAA上定义一个偏序关系，如果aaa是bbb的后缀，则a'#'结尾）之总和。可以将AAA中所有字符串ttt翻转一下然后加入Trie中，将沿途的所有节点做标记（除了插入完成之后所到达的节点），然后再求所有未标记的节点所对应的字符串的长度（加111）的总和即可。代码如下：

class Solution {public:struct Node {Node* ne[26];bool valid;Node() : valid(true) { fill(ne, ne + 26, nullptr); }};Node* root;void insert(string& s, unordered_map& mp) {auto* p = root;for (char ch : s) {p->valid = false;int idx = ch - 'a';if (!p->ne[idx]) p->ne[idx] = new Node();p = p->ne[idx];}mp[p] = s.size();}int minimumLengthEncoding(vector& words) {root = new Node();unordered_map mp;for (int i = 0; i < words.size(); i++) {auto& s = words[i];reverse(s.begin(), s.end());insert(s, mp);}int res = 0;for (auto& [p, len] : mp)if (p->valid) res += len + 1;return res;}
};

时空复杂度O(∑lAi)O(\sum l_{A_i})O(∑lAi​​)。