贵州省城乡与住房建设部网站,关于建设企业网站的请示,电商网站的二级菜单怎么做,自己买个服务器有什么用文章目录1. 题目2. 解题2.1 反转字符串字符查找2.2 后缀树1. 题目
给定一个单词列表#xff0c;我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
例如#xff0c;如果这个列表是 [time, me, bell]#xff0c;我们就可以将其…
文章目录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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 反转字符串字符查找
将每个字符串反转并按长度降序排序后面出现的单词在前面累积的字符串中查找到了且为“后缀”反转后的前缀则不用加入答案字符串中否则添加 #和字符串
class Solution {
public:int minimumLengthEncoding(vectorstring 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采用哈希表存储子节点实现如下
class Trie
{
public:unordered_mapchar,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(vectorstring 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 count1;// 1是 ‘#’return;}for(auto it root-m.begin(); it ! root-m.end(); it)dfs(it-second, count1);}
};
