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