0820. Short Encoding of Words¶
题目信息¶
- 题号:
0820
- 难度:
Medium
- 主题:
字符串、后缀共享、最短编码
- 原题:
- 重点:
每个单词必须在参考字符串中紧邻字符 # 结束;作为其他单词后缀的单词可以共享同一段编码,重复单词也无需重复占用
题目重述¶
给定字符串数组 words。需要构造一个参考字符串 s,其中若干单词后面紧跟分隔符 #。同时为每个输入单词指定一个起始下标,使从该下标读到下一个 # 之前的内容恰好等于该单词。
多个单词可以共享参考字符串中的字符。例如一个单词是另一个单词的后缀时,它可以从较长单词内部开始读取;相同单词的多个输入实例也可以使用同一位置。请返回满足全部单词的参考字符串最短长度,不需要返回字符串本身或下标。
1 <= words.length <= 2000,每个单词长度在 [1, 7] 范围内,且只包含小写英文字母。
自建示例¶
多个后缀共享较长单词的编码:
输入:words = ["code","ode","de","go"]
输出:8
解释:可使用参考字符串 "code#go#",长度为 8;ode 和 de 都能从 code 内部对应位置读到同一个 #,无需单独编码。
重复单词共享同一位置:
输入:words = ["x","x"]
输出:2
解释:两个输入实例可以共同使用参考字符串 "x#" 中从下标 0 开始的位置,因此只需编码一次。单字符加分隔符的最短长度为 2。