单词的压缩编码-13.字典树

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 <= 2000
• 1 <= words[i].length <= 7
• words[i] 仅由小写字母组成

算法一：
从题目可看出，只有是子串并且该子串是后缀，则会被“吃掉”；

1. 因此采用排序的方式，让字符串长的在前面，短的在后面，这样前面的长字符串，尽可能多的“吃掉”后面的后缀子串；
2. 同时采用标记位数组标记后缀子串，后缀子串一旦标记则就相当于被“吃掉”，不会记录长度；
3. 剩下的没有被标记的字符串，则遍历其长度，并每个长度+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，但是不是最优算法，所以要采用字典树来实现；