leetcode 820. Short Encoding of Words 单词的压缩编码

Problem: 820. Short Encoding of Words 单词的压缩编码

解题过程

使用了字典树，哈希表，集合，哈希表用来表示是否已经加入到字符串内，字典树用一个index表示单词的索引，首先用集合去重，然后清空words，放入去重以后的字符串，然后按照长度排序的

排序以后放入到字典树中，倒序放入的，并在第一个字母标记isEnd= true和索引index，像单词time 和 me，放入以后从最长的开始遍历字典树，emit就包含了time和me，构造字符串并标记状态，防止重复访问，最后返回字符串长度

Code

class tries{ public: int index; bool isEnd = false; tries* arr[26] = {nullptr}; tries() { for(int i = 0; i < 26; i++) { arr[i] = nullptr; } } }; class Solution { public: int minimumLengthEncoding(vector<string>& words) { tries* root = new tries, *ptr; unordered_set<string> te; for(string& s : words) { te.insert(s); } words.clear(); for(auto s : te) { words.push_back(s); } function<bool(string, string)> fun = [&](string a, string c){ return a.size() > c.size(); }; sort(words.begin(), words.end(), fun); for(int i = 0; i < words.size(); i++) { ptr = root; char ch; for(int j = words[i].size() - 1; j >= 0; j--) { ch = words[i][j]; if(ptr->arr[ch-'a']==nullptr) { ptr->arr[ch-'a'] = new tries; } ptr = ptr->arr[ch-'a']; if(j == 0) { ptr->isEnd = true; ptr->index = i; } } } vector<bool> status(words.size(), false); string tg; for(int i = 0; i < words.size(); i++) { if(status[i] == true) continue; status[i] = true; ptr = root; char ch; for(int j = words[i].size() - 1; j >= 0; j--) { ch = words[i][j]; ptr = ptr->arr[ch-'a']; if(ptr->isEnd == true) { status[ptr->index] = true; } } tg += words[i] + "#"; } return tg.size(); } };