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

题目描述
你需要设计一个单词缩写系统，该系统能将输入的单词转换为其缩写形式。缩写规则为：如果单词长度小于等于2，则缩写为原单词本身；否则缩写为首字母 + 中间字符数量 + 尾字母。例如：

• "it" → "it"（长度2，不变）
• "dog" → "d1g"（首字母d，中间字符数1，尾字母g）
• "internationalization" → "i18n"（首字母i，中间字符数18，尾字母n）

但是，当不同的单词可能产生相同的缩写时，需要处理冲突。例如：

• "hello" → "h3o"
• "hollow" → "h4w"（不冲突）
• 但假设有单词"hyperion"缩写为"h6n"，而"habitation"也缩写为"h6n"，这就产生了冲突。

请设计一个类WordAbbr，支持以下操作：

1. addWord(word)：将单词添加到系统中。
2. isUnique(word)：检查单词缩写是否唯一。即，如果系统中已添加的单词里，与word具有相同缩写的单词只有word本身（或没有其他单词），则返回true；否则返回false。

示例

操作：
addWord("hello")
addWord("hello")
isUnique("hello") → true  # 只有"hello"自身产生缩写"h3o"
addWord("hyperion")
isUnique("hyperion") → false  # 缩写"h6n"也由"hello"产生？不对，这里需要重新检查

实际上，让我们看一个更清晰的例子：

addWord("deer")
addWord("door")
isUnique("deer") → false
解释："deer"缩写为"d2r"，"door"缩写也为"d2r"，有冲突，所以不唯一。
isUnique("door") → false  同理
addWord("cake")
isUnique("cake") → true  缩写"c2e"唯一

解题过程

我们将循序渐进地设计这个系统，核心是使用哈希表来跟踪每个缩写对应的单词集合，以高效处理冲突检测。

步骤1：确定数据结构
我们需要存储每个缩写对应的所有单词。因为同一缩写可能对应多个单词，所以用哈希表（字典/映射）来存储：

• 键（key）：单词的缩写（字符串）。
• 值（value）：具有该缩写的所有单词的集合（用集合Set存储，避免重复单词重复计数）。

另外，我们还需要存储所有添加过的单词，以支持重复添加同一单词时，集合能去重。但注意题目中addWord可以重复添加同一单词，但isUnique检查时，重复的同一个单词不视为冲突（即自身不算冲突）。因此，我们需要记录每个单词的出现次数，以便在检查唯一性时准确判断。我们可以用另一个哈希表wordCount来记录每个单词被添加的次数。

步骤2：设计缩写生成函数
根据规则，实现一个辅助函数abbreviate(word)：

1. 如果单词长度n <= 2，直接返回原单词。
2. 否则，缩写为：word[0] + str(n-2) + word[n-1]。

注意：中间字符数量是n-2，因为要去掉首尾两个字符。

步骤3：实现addWord操作

1. 生成单词的缩写abbr。
2. 在wordCount中增加该单词的计数。
3. 将单词添加到缩写对应的集合中（在集合中，同一单词只存储一次，但我们需要通过计数来判断是否唯一，所以集合中存储单词即可，计数单独用wordCount记录）。

具体逻辑：

• 如果wordCount[word]为0（即第一次添加），则将其加入缩写对应的集合。
• 否则（已添加过），只增加计数，不重复加入集合（因为集合自动去重，但这里我们明确不重复添加，以便isUnique逻辑简单）。

步骤4：实现isUnique操作

1. 生成单词的缩写abbr。
2. 在哈希表中查找该缩写对应的单词集合。
3. 如果集合中只有当前单词本身，则返回true。注意：即使集合中只有当前单词，但如果该单词被添加了多次，也视为唯一（因为都是同一个单词）。
4. 如果集合为空（即没有单词具有这个缩写），也返回true。
5. 否则返回false。

步骤5：逐步推演示例
假设我们执行：

• addWord("deer")
  • 缩写："d2r"
  • wordCount["deer"] = 1
  • 缩写表：{"d2r": {"deer"}}
• addWord("door")
  • 缩写："d2r"
  • wordCount["door"] = 1
  • 缩写表：{"d2r": {"deer", "door"}}
• isUnique("deer")
  • 缩写："d2r"
  • 对应的集合为{"deer", "door"}，包含其他单词，返回false。
• addWord("cake")
  • 缩写："c2e"
  • 缩写表：{"d2r": {"deer", "door"}, "c2e": {"cake"}}
• isUnique("cake")
  • 缩写"c2e"对应集合只有{"cake"}，返回true。

步骤6：边界情况处理

• 单词长度≤2时，缩写就是单词本身，但系统仍将其视为一种缩写（例如"it"的缩写是"it"）。如果另一个单词也是"it"，则它们相同，不冲突（因为是同一单词）。但如果另一个单词是"is"，缩写为"is"，则不同缩写，不冲突。
• 重复添加同一单词多次：例如两次添加"hello"，wordCount["hello"]=2，缩写集合中只有{"hello"}，isUnique("hello")应返回true（因为只有自身）。

步骤7：代码框架（Python风格）

class WordAbbr:
    def __init__(self):
        self.abbrMap = {}  # 缩写 -> 单词集合
        self.wordCount = {}  # 单词 -> 计数

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

    def addWord(self, word: str) -> None:
        abbr = self.abbreviate(word)
        # 更新单词计数
        self.wordCount[word] = self.wordCount.get(word, 0) + 1
        # 如果是第一次添加，才加入缩写集合
        if self.wordCount[word] == 1:
            self.abbrMap.setdefault(abbr, set()).add(word)

    def isUnique(self, word: str) -> bool:
        abbr = self.abbreviate(word)
        # 如果缩写不存在于abbrMap，说明没有单词有这个缩写，唯一
        if abbr not in self.abbrMap:
            return True
        # 获取具有该缩写的所有单词集合
        words = self.abbrMap[abbr]
        # 如果集合中只有当前单词本身，则唯一
        return words == {word}

步骤8：复杂度分析

• 缩写生成：O(1)。
• addWord：O(1)（哈希表插入和集合添加平均O(1)）。
• isUnique：O(1)（哈希表查找和集合比较）。
• 空间复杂度：O(N)，N为添加的不同单词数量。

关键点
本题的核心是通过哈希表将缩写映射到单词集合，从而在检查唯一性时快速查看是否有其他单词共享同一缩写。注意处理同一单词多次添加的情况，确保自身不与自己冲突。这种设计模式在实际中可用于词典缩写、自动补全等场景。