Medium

题目描述

单词数组 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"
words[1] = "me" ，s 开始于 indices[1] = 2 到下一个 '#' 的子字符串是 "me"
words[2] = "bell" ，s 开始于 indices[2] = 5 到下一个 '#' 的子字符串是 "bell"

示例 2：

输入：words = ["t"]
输出：2
解释：一组有效编码为 s = "t#" 和 indices = [0] 。

提示：

  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 7
  • words[i] 仅由小写字母组成

解题思路

这道题的核心是理解编码规则：如果一个单词是另一个单词的后缀，那么它可以被包含在更长的单词中，不需要单独编码。

思路分析：

问题转化为：找出所有不是其他单词后缀的单词，这些单词的长度之和加上分隔符的数量就是答案。

解法一：集合去重法（推荐）

  1. 将所有单词放入集合中
  2. 遍历每个单词的所有后缀，如果后缀存在于集合中，则从集合中移除
  3. 剩下的单词就是需要单独编码的，计算总长度

解法二：字典树法 构建反向字典树（从单词末尾开始插入），叶子节点对应的单词需要单独编码。

解法三：排序 + 后缀判断 按长度降序排序，对于每个单词，检查是否为前面更长单词的后缀。

集合去重法最直观且效率高，是最优解法。

代码实现

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        unordered_set<string> wordSet(words.begin(), words.end());
        
        for (const string& word : words) {
            for (int i = 1; i < word.length(); i++) {
                wordSet.erase(word.substr(i));
            }
        }
        
        int result = 0;
        for (const string& word : wordSet) {
            result += word.length() + 1;
        }
        
        return result;
    }
};

class Solution:
    def minimumLengthEncoding(self, words: List[str]) -> int:
        word_set = set(words)
        
        for word in words:
            for i in range(1, len(word)):
                word_set.discard(word[i:])
        
        return sum(len(word) + 1 for word in word_set)

public class Solution {
    public int MinimumLengthEncoding(string[] words) {
        var wordSet = new HashSet<string>(words);
        
        foreach (string word in words) {
            for (int i = 1; i < word.Length; i++) {
                wordSet.Remove(word.Substring(i));
            }
        }
        
        int result = 0;
        foreach (string word in wordSet) {
            result += word.Length + 1;
        }
        
        return result;
    }
}

var minimumLengthEncoding = function(words) {
    const wordSet = new Set(words);
    
    for (const word of words) {
        for (let i = 1; i < word.length; i++) {
            wordSet.delete(word.substring(i));
        }
    }
    
    let result = 0;
    for (const word of wordSet) {
        result += word.length + 1;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型集合去重法
时间复杂度O(∑w²) 其中 w 是单词长度
空间复杂度O(∑w) 存储所有单词的集合