给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。
对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。
那么成功对给定单词列表进行编码的最小字符串长度是多少呢？
示例：
输入: words = ["time", "me", "bell"]
输出: 10
说明: S = "time#bell#" ， indexes = [0, 2, 5] 。
提示：
1 <= words.length <= 2000
1 <= words[i].length <= 7
每个单词都是小写字母 。
class TrieNode{ TrieNode* children[26]; public: int count; TrieNode(){ for(int i = 0; i < 26; i++){ children[i] = NULL; } count = 0; } TrieNode* get(char c){ if(children[c-‘a‘] == NULL){ children[c-‘a‘] = new TrieNode(); count+=1; } return children[c-‘a‘]; } }; class Solution { public: int minimumLengthEncoding(vector<string>& words) { TrieNode* trie = new TrieNode(); unordered_map<TrieNode*, int> nodes; for(int i = 0; i < words.size(); i++){ string word = words[i]; TrieNode* cur = trie; for(int j = word.length()-1; j >= 0; j--){ cur = cur->get(word[j]); } nodes[cur] = i; } int res = 0; for(const auto& [node, idx]: nodes){ if(node->count == 0) res += (words[idx].length() + 1); } return res; } };
解题思路：
这里主要是用到字典树的数据结构。
每个节点为一个26维的数组，其实可以把26个元素全是NULL的数组理解为一个空指针。
把所有单词逆序逐个单词存到字典树里，则叶子节点的个数就是压缩后的单词个数。
再找到每个叶子节点所对应的单词，求其长度，再+1，即是答案。
P.S. 每个节点除了有一个数组，还有一个count，这个count记录的是有多少个单词到达了这个字母。所以叶子节点的count是0。
NULL->e->m->i->t->NULL
count 0 2 2 1 1 0
原文：https://www.cnblogs.com/olajennings/p/12589708.html