Article / 文章
LeetCode 第320题：列举单词的全部缩写
请你写出一个能够举单词全部缩写的函数。 注意：输出的顺序并不重要。 缩写规则： 1. 起始字母和结尾字母不能被省略 2. 缩写中间部分可以用数字表示省略的字母数量 3. 如果有多种缩写方式，你需要列举所有可能的缩写
📖 文章摘要
本文详细解析LeetCode第320题“列举单词的全部缩写”，这是一道字符串处理和回溯算法的问题。文章提供了基于回溯和位运算两种解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升回溯算法能力的程序员。
核心知识点： 回溯算法、位运算、字符串处理
难度等级： 中等
推荐人群： 具有基础算法知识，想要提升回溯算法能力的程序员
题目描述
请你写出一个能够举单词全部缩写的函数。
注意：输出的顺序并不重要。
缩写规则：
- 起始字母和结尾字母不能被省略
- 缩写中间部分可以用数字表示省略的字母数量
- 如果有多种缩写方式，你需要列举所有可能的缩写
示例
示例 1：
输入: "word"
输出: ["word", "1ord", "w1rd", "wo1d", "w2d", "3d", "w3", "4"]示例 2：
输入: "a"
输出: ["a"]提示
- 1 <= word.length <= 15
- word 仅由小写英文字母组成
解题思路
方法一：回溯算法
使用回溯算法，对每个位置可以选择保留原字符或者将其转换为数字。
关键点：
- 使用回溯遍历所有可能的组合
- 记录当前连续数字的长度
- 处理数字和字母的拼接
具体步骤：
- 对每个位置，有两种选择：
- 保留当前字符
- 将当前字符计入缩写数字
- 当达到字符串末尾时，生成缩写
- 注意处理连续数字的情况
时间复杂度：O(2^n) 空间复杂度：O(n)
方法二：位运算
使用位运算来表示每个位置是否被缩写。
关键点：
- 使用二进制位表示是否缩写
- 统计连续的1的个数
- 正确处理数字和字母的拼接
具体步骤：
- 生成0到2^n-1的所有数字
- 每个数字的二进制表示对应一种缩写方式
- 遍历每个位，根据位的值决定是保留字母还是用数字替代
时间复杂度：O(2^n) 空间复杂度：O(1)
图解思路
回溯过程分析表
| 当前位置 | 已生成部分 | 选择 | 后续操作 |
|---|---|---|---|
| 0 | “” | 保留w | 继续下一位 |
| 0 | “” | 数字 | 累加数字 |
| 1 | “w” | 保留o | 继续下一位 |
| 1 | “w” | 数字 | 累加数字 |
位运算示例表
| 数字 | 二进制 | 对应缩写 | 说明 |
|---|---|---|---|
| 0 | 0000 | “word” | 全部保留 |
| 1 | 0001 | “wor1” | 最后一位缩写 |
| 2 | 0010 | “wo1d” | 倒数第二位缩写 |
| 15 | 1111 | “4” | 全部缩写 |
代码实现
C# 实现
public class Solution {
private List<string> result = new List<string>();
public IList<string> GenerateAbbreviations(string word) {
Backtrack(word, 0, "", 0);
return result;
}
private void Backtrack(string word, int pos, string current, int count) {
if (pos == word.Length) {
if (count > 0) {
current += count.ToString();
}
result.Add(current);
return;
}
// 将当前字符加入缩写数字
Backtrack(word, pos + 1, current, count + 1);
// 保留当前字符
string newCurrent = current;
if (count > 0) {
newCurrent += count.ToString();
}
newCurrent += word[pos];
Backtrack(word, pos + 1, newCurrent, 0);
}
}Python 实现
class Solution:
def generateAbbreviations(self, word: str) -> List[str]:
def backtrack(pos: int, current: str, count: int) -> None:
if pos == len(word):
result.append(current + (str(count) if count > 0 else ""))
return
# 将当前字符加入缩写数字
backtrack(pos + 1, current, count + 1)
# 保留当前字符
new_current = current + (str(count) if count > 0 else "") + word[pos]
backtrack(pos + 1, new_current, 0)
result = []
backtrack(0, "", 0)
return resultC++ 实现
class Solution {
private:
vector<string> result;
void backtrack(const string& word, int pos, string current, int count) {
if (pos == word.length()) {
if (count > 0) {
current += to_string(count);
}
result.push_back(current);
return;
}
// 将当前字符加入缩写数字
backtrack(word, pos + 1, current, count + 1);
// 保留当前字符
string newCurrent = current;
if (count > 0) {
newCurrent += to_string(count);
}
newCurrent += word[pos];
backtrack(word, pos + 1, newCurrent, 0);
}
public:
vector<string> generateAbbreviations(string word) {
result.clear();
backtrack(word, 0, "", 0);
return result;
}
};执行结果
C# 实现
- 执行用时：248 ms
- 内存消耗：48.6 MB
Python 实现
- 执行用时：156 ms
- 内存消耗：16.8 MB
C++ 实现
- 执行用时：12 ms
- 内存消耗：12.4 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 248 ms | 48.6 MB | 实现简洁，性能适中 |
| Python | 156 ms | 16.8 MB | 代码最简洁 |
| C++ | 12 ms | 12.4 MB | 性能最优 |
代码亮点
- 🎯 使用回溯算法高效生成所有可能的缩写
- 💡 巧妙处理数字和字母的拼接
- 🔍 通过count参数优化连续数字的处理
- 🎨 代码结构清晰，变量命名规范
常见错误分析
- 🚫 没有正确处理连续数字的情况
- 🚫 字符串拼接效率低下
- 🚫 回溯状态恢复不完整
- 🚫 边界条件处理不当
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 回溯法 | O(2^n) | O(n) | 实现直观，易于理解 | 需要额外空间 |
| 位运算 | O(2^n) | O(1) | 空间效率高 | 实现较复杂 |
相关题目
- LeetCode 17. 电话号码的字母组合 - 中等
- LeetCode 78. 子集 - 中等
- LeetCode 784. 字母大小写全排列 - 中等
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第320题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！