820. 单词的压缩编码
难度中等281
单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：
words.length == indices.length- 助记字符串
s以'#'字符结尾 - 对于每个下标
indices[i]，s的一个从indices[i]开始、到下一个'#'字符结束（但不包括'#'）的 子字符串 恰好与words[i]相等
给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。
示例 1：
输入：words = ["time", "me", "bell"]
输出：10
解释：一组有效编码为 s = "time#bell#" 和 indices = [0, 2, 5] 。
words[0] = "time" ，s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[1] = "me" ，s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell#"
words[2] = "bell" ，s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串，如加粗部分所示 "time#bell**#"
</pre>
示例 2：
输入：**words = ["t"]
输出：2
解释：一组有效编码为 s = "t#" 和 indices = [0] 。
</pre>
提示：
1 <= words.length <= 20001 <= words[i].length <= 7-
words[i]仅由小写字母组成
算法一：
从题目可看出，只有是子串并且该子串是后缀，则会被“吃掉”；
- 因此采用排序的方式，让字符串长的在前面，短的在后面，这样前面的长字符串，尽可能多的“吃掉”后面的后缀子串；
- 同时采用标记位数组标记后缀子串，后缀子串一旦标记则就相当于被“吃掉”，不会记录长度；
- 剩下的没有被标记的字符串，则遍历其长度，并每个长度+1（表示#）；
class Solution {
public:
static bool Comp(const string &a, const string &b) // 注意写法
{
return a.size() > b.size();
}
bool IsContain(string &big, string &small)
{
int lenSmall = small.size();
int lenBig = big.size();
if (lenSmall > lenBig) {
return false;
}
int j = lenBig - 1;
for (int i = lenSmall - 1; (i >= 0) && (j >= 0); i--, j--) {
if (small[i] != big[j]) {
return false;
}
}
return true;
}
int minimumLengthEncoding(vector<string>& words)
{
vector<int> visit;
unsigned int lenCode = 0;
int len = words.size();
if (len == 0) {
return 0;
} else if (len == 1) {
return (words[0].size() + 1);
} else {
//visit.insert(visit.begin(), len, 0); //采用这种方式，leetcode出现执行出错。。。
for (int i = 0; i < len; i++) {
visit.push_back(0);
}
sort(words.begin(), words.end(), Comp);
for (int i = 0; i < len; i++) {
if (visit[i] != 0) {
continue;
}
for (int j = i + 1; j < len; j++) {
if (IsContain(words[i], words[j]) == true) {
visit[j] = 1; // 表明是子串，被吃掉
}
}
}
for (int i = 0; i < len; i++) {
if (visit[i] == 0) {
lenCode = lenCode + (words[i]).size() + 1; // 1表示‘#’
}
}
return lenCode;
}
return lenCode;
}
};
算法二
算法一虽然AC，但是不是最优算法，所以要采用字典树来实现；
