class Solution {
public:
int minimumLengthEncoding(vector<string>& words) {
}
};
剑指 Offer II 065. 最短的单词编码
单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：
words.length == indices.lengths 以 '#' 字符结尾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 <= 20001 <= words[i].length <= 7words[i] 仅由小写字母组成
注意：本题与主站 820 题相同： https://leetcode.cn/problems/short-encoding-of-words/
原站题解
python3 解法, 执行用时: 132 ms, 内存消耗: 17.1 MB, 提交时间: 2022-11-17 16:38:24
class Solution:
def minimumLengthEncoding(self, words: List[str]) -> int:
words = list(set(words)) #remove duplicates
#Trie is a nested dictionary with nodes created
# when fetched entries are missing
Trie = lambda: collections.defaultdict(Trie)
trie = Trie()
#reduce(..., S, trie) is trie[S[0]][S[1]][S[2]][...][S[S.length - 1]]
nodes = [reduce(dict.__getitem__, word[::-1], trie)
for word in words]
#Add word to the answer if it's node has no neighbors
return sum(len(word) + 1
for i, word in enumerate(words)
if len(nodes[i]) == 0)
python3 解法, 执行用时: 76 ms, 内存消耗: 15.3 MB, 提交时间: 2022-11-17 16:37:59
class Solution:
def minimumLengthEncoding(self, words: List[str]) -> int:
good = set(words)
for word in words:
for k in range(1, len(word)):
good.discard(word[k:])
return sum(len(word) + 1 for word in good)