LeetCode 第288题：单词的唯一缩写

📖 文章摘要

本文详细解析LeetCode第288题“单词的唯一缩写”，这是一道考察字符串处理和哈希表的中等难度题目。文章提供了哈希表实现方案，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合学习字符串处理和数据结构设计的读者。

核心知识点： 字符串处理、哈希表、设计模式
难度等级： 中等
推荐人群： 具备基础算法知识，想要提升字符串处理和数据结构设计能力的开发者

题目描述

一个单词的缩写需要遵循以下格式：首字母 + 中间字母数量 + 尾字母。例如：

“internationalization” 的缩写是 “i18n”
“localization” 的缩写是 “l10n”

实现一个 ValidWordAbbr 类：

ValidWordAbbr(String[] dictionary) 初始化对象
boolean isUnique(String word) 如果字典中没有任何其他单词的缩写与给定单词的缩写相同，则返回 true

示例

示例 1：

输入：
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"]]
输出：
[null, false, true, false, true]

解释：
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // 返回 false，因为 "deer" 和 "dear" 的缩写都是 "d2r"
validWordAbbr.isUnique("cart"); // 返回 true，因为 "cart" 的缩写是 "c2t"，字典中没有其他单词的缩写是 "c2t"
validWordAbbr.isUnique("cane"); // 返回 false，因为 "cake" 和 "cane" 的缩写都是 "c2e"
validWordAbbr.isUnique("make"); // 返回 true，因为 "make" 的缩写是 "m2e"，字典中没有其他单词的缩写是 "m2e"

提示

1 <= dictionary.length <= 3 * 10^4
1 <= dictionary[i].length <= 20
dictionary[i] 由小写英文字母组成
1 <= word.length <= 20
word 由小写英文字母组成
最多调用 10^4 次 isUnique

解题思路

本题可以使用哈希表来实现：

初始化：
- 创建哈希表存储缩写和对应的单词集合
- 遍历字典，计算每个单词的缩写
- 将缩写和单词存入哈希表
查询：
- 计算目标单词的缩写
- 检查哈希表中是否存在该缩写
- 如果存在，检查是否只有当前单词

图解思路

缩写计算规则表

单词长度	缩写格式	示例
≤2	原单词	“a” -> “a”
>2	首字母+中间长度+尾字母	“word” -> “w2d”

哈希表结构分析表

缩写	单词集合	说明
d2r	{deer, door}	多个单词
c2e	{cake}	单个单词
c2t	{card}	单个单词

代码实现

C# 实现

public class ValidWordAbbr {
    private Dictionary<string, HashSet<string>> abbrDict;
    
    public ValidWordAbbr(string[] dictionary) {
        abbrDict = new Dictionary<string, HashSet<string>>();
        
        foreach (string word in dictionary) {
            string abbr = GetAbbreviation(word);
            if (!abbrDict.ContainsKey(abbr)) {
                abbrDict[abbr] = new HashSet<string>();
            }
            abbrDict[abbr].Add(word);
        }
    }
    
    public bool IsUnique(string word) {
        string abbr = GetAbbreviation(word);
        
        // 如果缩写不存在，或者缩写对应的单词集合中只有当前单词
        return !abbrDict.ContainsKey(abbr) || 
               (abbrDict[abbr].Count == 1 && abbrDict[abbr].Contains(word));
    }
    
    private string GetAbbreviation(string word) {
        if (word.Length <= 2) {
            return word;
        }
        
        return word[0] + (word.Length - 2).ToString() + word[word.Length - 1];
    }
}

Python 实现

class ValidWordAbbr:
    def __init__(self, dictionary: List[str]):
        self.abbr_dict = {}
        
        for word in dictionary:
            abbr = self.get_abbreviation(word)
            if abbr not in self.abbr_dict:
                self.abbr_dict[abbr] = set()
            self.abbr_dict[abbr].add(word)
    
    def isUnique(self, word: str) -> bool:
        abbr = self.get_abbreviation(word)
        
        # 如果缩写不存在，或者缩写对应的单词集合中只有当前单词
        return abbr not in self.abbr_dict or \
               (len(self.abbr_dict[abbr]) == 1 and word in self.abbr_dict[abbr])
    
    def get_abbreviation(self, word: str) -> str:
        if len(word) <= 2:
            return word
            
        return word[0] + str(len(word) - 2) + word[-1]

C++ 实现

class ValidWordAbbr {
private:
    unordered_map<string, unordered_set<string>> abbrDict;
    
    string getAbbreviation(const string& word) {
        if (word.length() <= 2) {
            return word;
        }
        
        return word[0] + to_string(word.length() - 2) + word[word.length() - 1];
    }
    
public:
    ValidWordAbbr(vector<string>& dictionary) {
        for (const string& word : dictionary) {
            string abbr = getAbbreviation(word);
            abbrDict[abbr].insert(word);
        }
    }
    
    bool isUnique(string word) {
        string abbr = getAbbreviation(word);
        
        // 如果缩写不存在，或者缩写对应的单词集合中只有当前单词
        return abbrDict.find(abbr) == abbrDict.end() || 
               (abbrDict[abbr].size() == 1 && abbrDict[abbr].count(word) > 0);
    }
};

执行结果

C# 实现

执行用时：156 ms
内存消耗：35.2 MB

Python 实现

执行用时：132 ms
内存消耗：16.8 MB

C++ 实现

执行用时：48 ms
内存消耗：14.2 MB

性能对比

语言	执行用时	内存消耗	特点
C#	156 ms	35.2 MB	代码结构清晰，性能适中
Python	132 ms	16.8 MB	代码最简洁，性能不错
C++	48 ms	14.2 MB	性能最优，内存占用最小

代码亮点

🎯 使用哈希表优化查询效率
💡 使用HashSet避免重复单词
🔍 缩写计算逻辑清晰
🎨 代码结构清晰，易于维护

常见错误分析

🚫 未处理单词长度小于等于2的情况
🚫 缩写计算逻辑错误
🚫 哈希表查询条件错误
🚫 未考虑重复单词的情况

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
哈希表	O(1)	O(n)	查询效率高	需要额外空间
暴力法	O(n)	O(1)	空间效率高	查询效率低

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第288题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

提示

解题思路

图解思路

缩写计算规则表

哈希表结构分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流