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 List

class 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 = 0
        for node, length in nodes.items():
            if not node.children:  # 叶子节点（无子节点）
                total += length
        return total

if __name__ == "__main__":
    # 测试用例
    test1 = Solution().minimumLengthEncoding(["time", "me", "bell"])  # 10
    test2 = Solution().minimumLengthEncoding(["t"])  # 2
    print(test1, test2)