给定一个单词列表,我们将这个列表编码成一个索引字符串 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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
#和字符串
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--]);
}
};
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)// 是叶子节点
{
len += count+1;// +1是 ‘#’
return;
}
for(auto it = root->m.begin(); it != root->m.end(); ++it)
dfs(it->second, count+1);
}
};