本文主要是介绍200330题（820.单词的压缩编码（字典树）），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
从0位置开始遍历字符串S，遇到#停止，得到time 从2位置开始遍历字符串S，遇到#停止，得到me 从5位置开始遍历字符串S，遇到#停止，得到bell.
字典树的建立详见实现 Trie (前缀树、字典树)
法1思路：字典树：根据列表中单词的长度由长到短进行排序，排好序后对每个单词反转顺序，最后再插入字典树，插入时通过标志位isNew判断是否为新单词即可。
class Trie {
private:bool isEnd;Trie* next[26];
public:Trie(){isEnd = false;memset(next, 0, sizeof(next));}int insert(string word) {bool isNew = false;//判断是否为新单词Trie* node = this;for (char c : word){if (node->next[c - 'a'] == NULL){node->next[c - 'a'] = new Trie();isNew = true;//是新单词（因为创建了新结点，所以是新单词）}node = node->next[c - 'a'];}node->isEnd = true;return isNew ? word.length() + 1 : 0;//+1是因为还有#}};class Solution {
public:bool static cmp(const string str1, const string str2){return str1.length() > str2.length();}int minimumLengthEncoding(vector<string>& words){Trie*trie = new Trie();//根据列表中单词的长度由长到短进行排序，排好序后对每个单词反转顺序，最后再插入字典树sort(words.begin(), words.end(), cmp);for (int i = 0; i < words.size(); i++){reverse(words[i].begin(), words[i].end());}int res = 0;for (string word : words){res += trie->insert(word);}return res;}
};
法2思路：利用set去重，然后对于set中的每个字符串，删除set中与其后缀重复的字符串。
class Solution {
public:int minimumLengthEncoding(vector<string>& words) {unordered_set<string>myset(words.begin(), words.end());//利用迭代器构造set对象（自动去重）for (const string& s : myset){for (int i = 1; i < s.size(); i++){myset.erase(s.substr(i));}}int len = 0;for (auto it = myset.begin(); it != myset.end(); it++){len += (*it).size() + 1;}return len;}
};
string s = "abcde";
cout << s.substr(1);//返回的是string类的对象，结果为bcde
这篇关于200330题（820.单词的压缩编码（字典树））的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
