文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 反轉字符串+字符查找
    • 2.2 后綴樹

1. 題目

給定一個單詞列表，我們將這個列表編碼成一個索引字符串 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 每個單詞都是小寫字母 。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/short-encoding-of-words
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

2. 解題

2.1 反轉字符串+字符查找

• 將每個字符串反轉，并按長度降序排序
• 后面出現(xiàn)的單詞在前面累積的字符串中查找到了，且為“后綴”（反轉后的前綴），則不用加入答案字符串中，否則添加 #和字符串

class Solution { public:int minimumLengthEncoding(vector<string>& words) {for(string& w : words)reverse(w);//反轉每個字符串sort(words.begin(), words.end(),[&](string& a, string& b){return a.size() > b.size();//長的在前});string ans;for(string& w : words){size_t pos = ans.find(w);//在ans里查找，沒找到，或者，找到了，但是不是反轉后的前綴if(pos == string::npos || ans[pos-1]!='#')// 注意["me" ,"mean"]之類的例子ans += "#"+w;}return ans.size();}void reverse(string& s){int i = 0, j = s.size()-1;while(i < j)swap(s[i++],s[j--]);} };

2.2 后綴樹

• 將字符串逆序插入前綴樹（Trie）
• 采用哈希表存儲子節(jié)點，實現(xiàn)如下

class Trie { public:unordered_map<char,Trie*> m;// bool isEnd = false;void rev_insert(string& s){Trie* root = this;for(int i = s.size()-1; i >= 0; --i){if(!(root->m).count(s[i])){Trie* node = new Trie();root->m.insert(make_pair(s[i],node));}root = root->m[s[i]];}// root->isEnd = true;} }; class Solution {int len = 0; public:int minimumLengthEncoding(vector<string>& words) {Trie *t = new Trie();for(string& w : words)t->rev_insert(w);dfs(t,0);return len;}void dfs(Trie * root, int count){if(root->m.size()==0)// 是葉子節(jié)點{len += count+1;// +1是 ‘#’return;}for(auto it = root->m.begin(); it != root->m.end(); ++it)dfs(it->second, count+1);} };

總結

以上是生活随笔為你收集整理的LeetCode 820. 单词的压缩编码（后缀树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。