模拟哈希表实现单词缩写系统

题目描述

设计一个单词缩写系统，将给定的单词列表转换为唯一缩写。缩写规则为：<首字母><中间省略的字母个数><尾字母>。例如：

• "internationalization" → "i18n"
• "localization" → "l10n"

要求：

1. 如果缩写冲突（多个单词映射到同一缩写），系统需自动将冲突单词转换为原始单词，缩写改为保留原始单词。
2. 如果多个单词冲突，所有冲突单词都保留原始形式，不缩写。
3. 系统需支持查询：输入一个单词，返回其缩写或原始单词（根据冲突情况决定）。

示例：

输入单词列表：["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
输出缩写映射：
{
  "like": "like",       // 冲突处理
  "god": "god",         // 冲突处理
  "internal": "internal", // 冲突处理
  "me": "me",           // 长度≤2的单词不缩写
  "internet": "i6t",
  "interval": "interval", // 冲突处理
  "intension": "i8n",
  "face": "face",       // 冲突处理
  "intrusion": "i8n"    // 与"intension"缩写冲突，两者都不缩写
}

解题步骤

步骤1：理解缩写规则与冲突

1. 缩写公式：word[0] + (len-2) + word[-1]，例如 "internal"（长度8）→ "i6l"。
2. 不缩写的情况：
   • 单词长度 ≤ 2（例如 "me" → "me"）。
   • 缩写冲突时，所有冲突单词保留原形。
3. 冲突检测：需记录每个缩写对应的单词列表，如果列表长度 > 1，则这些单词都需保留原形。

步骤2：设计数据结构

• 使用两个哈希表：
  1. abbr_map：映射 缩写 → 单词列表，用于检测冲突。
  2. result_map：映射 原始单词 → 最终输出形式（缩写或原单词）。

步骤3：生成缩写函数

def abbreviate(word: str) -> str:
    if len(word) <= 2:
        return word
    return word[0] + str(len(word) - 2) + word[-1]

步骤4：第一次遍历——收集缩写冲突

1. 遍历单词列表，对每个单词生成缩写。
2. 将 (缩写, 单词) 存入 abbr_map 中。
3. 注意：长度 ≤ 2 的单词，其缩写就是原单词，但也要参与冲突检测（例如 "me" 和 "my" 都映射到自身，但它们是不同的单词，需作为冲突处理）。

示例中间状态：

单词 "internal" → 缩写 "i6l" → abbr_map["i6l"] = ["internal"]
单词 "interval" → 缩写 "i6l" → abbr_map["i6l"] = ["internal", "interval"]  # 冲突！

步骤5：第二次遍历——解决冲突并生成结果

1. 再次遍历每个单词：
   • 如果单词长度 ≤ 2，直接存入 result_map[word] = word。
   • 否则，查 abbr_map[缩写]：
     • 如果列表长度为 1，说明无冲突，result_map[word] = 缩写。
     • 如果列表长度 > 1，说明有冲突，result_map[word] = word（保留原形）。

示例：

• "internal" 的缩写 "i6l" 对应列表长度为 2，所以 result_map["internal"] = "internal"。
• "internet" 的缩写 "i6t" 无冲突，所以 result_map["internet"] = "i6t"。

步骤6：查询实现

• 给定一个单词，直接从 result_map 中返回对应的最终形式。

完整代码示例（Python）

class ValidWordAbbr:
    def __init__(self, words):
        self.abbr_map = {}  # 缩写 → 单词列表
        self.result_map = {}  # 单词 → 最终形式
        
        # 第一次遍历：收集缩写
        for w in words:
            abbr = self._abbreviate(w)
            if abbr not in self.abbr_map:
                self.abbr_map[abbr] = []
            self.abbr_map[abbr].append(w)
        
        # 第二次遍历：解决冲突
        for w in words:
            if len(w) <= 2:
                self.result_map[w] = w
            else:
                abbr = self._abbreviate(w)
                if len(self.abbr_map[abbr]) == 1:  # 无冲突
                    self.result_map[w] = abbr
                else:  # 有冲突
                    self.result_map[w] = w
    
    def _abbreviate(self, word):
        if len(word) <= 2:
            return word
        return word[0] + str(len(word) - 2) + word[-1]
    
    def get_abbr(self, word):
        return self.result_map.get(word, word)  # 默认返回原单词

# 测试
words = ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
solver = ValidWordAbbr(words)
for w in words:
    print(f"{w}: {solver.get_abbr(w)}")

输出：

like: like
god: god
internal: internal
me: me
internet: i6t
interval: interval
intension: intension
face: face
intrusion: intrusion

关键点总结

1. 冲突处理是核心：需先收集所有缩写映射，再根据冲突情况决定最终形式。
2. 长度≤2的单词：虽不缩写，但若多个短单词相同，也视为冲突（例如输入 ["me", "me"] 不冲突，但 ["me", "my"] 冲突，两者都保留原形）。
3. 时间复杂度：O(N)，其中 N 为单词总数；空间复杂度 O(N)，用于存储两个哈希表。

此系统可扩展为动态添加单词，但需重新检测冲突（例如新单词与旧单词缩写冲突时，需更新相关单词为原形）。