LeetCode 820 单词的压缩编码题解

LeetCode 820 单词的压缩编码题解

题目描述

题目链接
给定一个单词列表，将其编码为一个索引字符串S，格式为"单词1#单词2#…"。要求当某个单词是另一个单词的后缀时，该单词可以被省略。求最终编码字符串的最小长度。

解题思路

逆序前缀树法

1. 逆序建树：将单词逆序插入前缀树（如"time"→"emit"）
   逆序插入原理 将单词逆序后插入前缀树，使得：
   • me → em 成为 time → emit 的前缀路径
   • 在树结构中， em 路径会被 emit 完全包含
   • 通过检查路径末端是否为叶子节点判断是否需要保留
2. 统计叶子：只有叶子节点对应的单词需要保留
   • me 的逆序 em 路径末端仍有子节点（继续通向 i ）
   • time 的逆序 emit 路径末端是叶子节点
   • 因此只保留 time 和 bell
3. 计算长度：每个保留单词的长度+1（#号）
   每个保留单词的贡献长度为：
   原长度 + 1（#号分隔符）
   示例计算： time(4) + 1 + bell(4) + 1 = 10

完整代码实现

from typing import Listclass TrieNode:def __init__(self):self.children = {}  # 存储子节点class Solution:def minimumLengthEncoding(self, words: List[str]) -> int:# 1. 构建逆序前缀树root = TrieNode()# 用字典保存单词最后节点和单词长度nodes = {}for word in set(words):  # 去重处理node = root# 逆序插入字符for c in reversed(word):if c not in node.children:node.children[c] = TrieNode()node = node.children[c]nodes[node] = len(word) + 1  # 存储单词长度+1（#号）# 2. 统计需要保留的单词长度total = 0for node, length in nodes.items():if not node.children:  # 叶子节点（无子节点）total += lengthreturn totalif __name__ == "__main__":# 测试用例test1 = Solution().minimumLengthEncoding(["time", "me", "bell"])  # 10test2 = Solution().minimumLengthEncoding(["t"])  # 2print(test1, test2)