题目描述

给定一个单词列表，我们将这个列表编码成一个索引字符串 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
• 每个单词都是小写字母。

算法

(排序) $O(n \log n)$

1. 将数组中的每个字符串翻转后，从小到大按照字典序排序。这样，相邻的两个字符串可能能进行合并。
2. 从头开始扫描数组，比较当前字符串与下一个字符串，如果当前字符串是下一个字符串的前缀，则这两个字符串可以合并在一起；否则，答案加上当前字符串的长度再加 1。
3. 最后再加上最后一个字符串的长度再加 1。

时间复杂度

• 假设字符串的长度为常数，则排序的时间复杂度为 $O(n \log n)$，排序后扫描的时间复杂度为 $O(n)$，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 仅使用了常数个变量，空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    bool check(const string &x, const string &y) {
        if (x.length() > y.length())
            return false;
        for (int i = 0; i < x.length(); i++)
            if (x[i] != y[i])
                return false;

        return true;
    }

    int minimumLengthEncoding(vector<string>& words) {
        int n = words.size();
        for (int i = 0; i < n; i++)
            reverse(words[i].begin(), words[i].end());

        sort(words.begin(), words.end());

        int ans = 0;
        for (int i = 0; i < n - 1; i++) {
            if (!check(words[i], words[i + 1])) {
                ans += words[i].length() + 1;
            }
        }

        ans += words[n - 1].length() + 1;

        return ans;
    }
};