「每日LeetCode」2022年7月15日

本文最后更新于：2023年3月19日 晚上

820.单词的压缩编码

820.单词的压缩编码

Category Difficulty Likes Dislikes
algorithms Medium (51.54%) 281 -

Tags
Companies
单词数组 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#”
示例 2：
输入：words = [“t”] 输出：2 解释：一组有效编码为 s = “t#” 和 indices = [0] 。

提示：

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

Discussion | Solution

思路

使用 set，遍历每一个字符，取出当前遍历字符的所有后缀，判断是否在 set 中，是的话将其删除，最后得到无法压缩的单词组

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
 * @lc app=leetcode.cn id=820 lang=javascript
 *
 * [820] 单词的压缩编码
 */

// @lc code=start
/**
 * @param {string[]} words
 * @return {number}
 */
var minimumLengthEncoding = function (words) {
  const set = new Set(words);
  for (const word of words) {
    for (let i = word.length - 1; i > 0; i--) {
      const suff = word.slice(-i);
      if (set.has(suff)) set.delete(suff);
    }
  }
  return [...set.values()].join("#").length + 1;
};
// @lc code=end