题目描述
leetcode 第820题:单词的压缩编码
单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成,且满足:
words.length == indices.length
助记字符串 s 以 ‘# ‘ 字符结尾
对于每个下标 indices[i] ,s 的一个从 indices[i] 开始、到下一个 ‘# ‘ 字符结束(但不包括 ‘# ‘)的 子字符串 恰好与 words[i] 相等
给你一个单词数组 words ,返回成功对 words 进行编码的最小助记字符串 s 的长度 。
示例:
输入: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# “
解题方法一
字典树
原址题解
- 解题思路
构建字典树root
遍历单词数组words,将每个单词反转后存入root,构建后缀树
记录最小助记单词的长度minl
二次遍历words,查找一个单词是否存在于root
若存在时,minl累加当前单词的长度
- 复杂度
时间复杂度:O(n),n为单词数组words中的总字符数
空间复杂度:O(n)
- 代码实现
python3
1 | class Solution: |
php
1 | class Trie { |
解题方法二
哈希表
参照题解
- 解题思路
将单词数组words存入哈希表hashW
遍历words,如果words存在单词word1是word2的后缀,那么word2就不用考虑
所以我们从下标为1的位置循环截取word
当截取的单词是否存在于hashW时,就从hashW中删除单词
遍历完成后,计算一下hashW剩余的单词字符个数
对于hashW剩余的每个单词,还需计算助记字符’# ‘的个数
- 复杂度
时间复杂度:O(n^2)
空间复杂度:o(n)
- 代码实现
python3
1 | class Solution: |
php
1 | class Solution { |