教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是 AlgoNote「算法通关手册」中 LeetCode 0320「列举单词的全部缩写Generalized Abbreviation」的完整题解。文章以回溯算法为主线深入讲解广义缩写词的构造规则、有效与无效边界、决策树推导、完整可运行的 Python 实现并基于仓库中的回溯算法理论章节与系列姊妹题做源码级延展帮助读者系统掌握「枚举 剪枝」类字符串问题的通用解法。1. 题目理解什么是「广义缩写词」给定一个仅由小写英文字母组成的字符串word长度 $1 \le word.length \le 15$要求返回由word的所有可能「广义缩写词」组成的列表顺序不限。广义缩写词Generalized Abbreviation的构造规则先取任意数量的「不重叠、不相邻」的子字符串再用它们各自的长度十进制数字进行替换其余字符原样保留。以abcde为例以下缩写均有效a3e——bcd被替换为31bcd1——a和e分别被替换为15—— 整个abcde被替换为5abcde—— 不替换任何子串原样保留也属于一种缩写。以下缩写无效23ab→2cde→3无效因为两个被替换的子串相邻相邻本应合并为一个数字22deab→2bc→2无效因为两个被替换的子串重叠。示例 1输入word word 输出[4,3d,2r1,2rd,1o2,1o1d,1or1,1ord,w3,w2d,w1r1,w1rd,wo2,wo1d,wor1,word]示例 2输入word a 输出[1,a]从示例可以看出word长度为 4其全部缩写恰好有 $2^4 16$ 种与题目结论「每个位置有保留字符 / 作为数字两种选择」完全吻合。2. 核心解题思路回溯算法本题的标准解法是回溯算法Backtracking。在 AlgoNote 的 回溯算法理论章节 中给出过精确定义回溯算法通过递归和试错的方式逐步构建解当发现当前路径无法得到有效解时撤销上一步的选择即「回溯」返回到上一个决策点尝试其他路径。核心思想是「走不通就退回换条路再试」。2.1 状态设计设当前处理到字符串的第index个位置维护current当前已构建的缩写字符串is_prev_digit上一个位置是否为数字布尔值。其中is_prev_digit是本题的关键约束状态——它决定了当前位置能否开启一段新的数字替换若上一个位置不是数字is_prev_digit False说明当前可以开启一段新的数字替换若上一个位置是数字说明我们正处于一段连续替换之中不能在同一位置再次开启新数字否则会产生23这类相邻数字或22de这类重叠替换。2.2 决策分支对于位置index的字符每次递归有两种决策保留字符将word[index]直接追加到currentis_prev_digit置为False递归处理index 1作为数字仅当is_prev_digit False时枚举替换长度length从 1 到剩余字符数len(word) - index将str(length)追加到currentis_prev_digit置为True跳过length个字符递归处理index length。终止条件当index len(word)时所有字符都已处理完毕将current加入结果列表result。2.3 决策树推演以word为例从仓库 回溯算法理论章节 的「决策树」方法出发本题每一层代表一个字符位置每个节点代表一次「保留」或「替换」的选择。以word的根节点为例根节点index0选择保留w→ 进入index1或替换长度 14 → 生成1、2、3、4四个分支从1分支index1is_prev_digitTrue只能保留o→1o不能再开新数字这正是避免23、22de等无效缩写的约束体现从w分支index1is_prev_digitFalse可保留o→wo或替换 13 →w1、w2、w3……依此逐层展开叶子节点index4即为全部 16 个合法缩写。整棵搜索树完整覆盖了所有合法状态天然排除了「相邻数字」与「重叠替换」两类非法情况。2.4 算法正确性设字符串长度为 $n$每个位置有 2 种选择保留字符或作为数字的一部分理论上共有 $2^n$ 种组合。回溯算法通过「保留 / 替换」两个分支 is_prev_digit约束系统枚举所有有效组合不重不漏因此算法正确。3. 完整代码实现3.1 思路一回溯算法标准实现from typing import List class Solution: def generateAbbreviations(self, word: str) - List[str]: def backtrack(index, current, is_prev_digit): 回溯生成所有可能的缩写 Args: index: 当前处理的字符位置 current: 当前构建的缩写字符串 is_prev_digit: 上一个位置是否为数字 # 终止条件处理完所有字符 if index len(word): result.append(current) return # 选择 1保留当前字符 backtrack(index 1, current word[index], False) # 选择 2将当前字符作为数字的一部分 if not is_prev_digit: # 上一个位置不是数字可以开始新的数字 # 尝试从当前位置开始的所有可能的数字长度 for length in range(1, len(word) - index 1): backtrack(index length, current str(length), True) result [] backtrack(0, , False) return result实现要点说明backtrack的第三个参数is_prev_digit是防重复/防相邻数字的核心只有is_prev_digit False时才能开启新的数字替换分支替换分支中range(1, len(word) - index 1)枚举了从当前位置可以替换的全部可能长度确保word既能生成4整体替换也能生成3d、2rd等部分替换该实现完全符合仓库 回溯算法理论章节 给出的通用模板「定义回溯函数 → 明确终止条件 → 做选择 → 递归 → 撤销选择」本解法以不可变字符串拼接current ...传递状态天然实现了「选择不污染兄弟分支」的效果无需显式 pop 撤销。3.2 复杂度分析时间复杂度$O(2^n \times n)$其中 $n$ 是字符串长度。每个位置有 2 种选择共 $2^n$ 种合法组合每种组合需 $O(n)$ 时间构建字符串空间复杂度$O(2^n \times n)$。需要存储全部 $2^n$ 个缩写结果每个结果长度为 $O(n)$若只计算递归栈则递归深度为 $O(n)$。3.3 思路二位运算枚举标签补充视角本题标签为「位运算、字符串、回溯」。除了回溯也可以借助位运算以「掩码枚举」的视角理解同一问题将每个位置视作一个二进制位1表示该位置被纳入替换、0表示保留原字符。遍历mask从0到 $2^n - 1$ 共 $2^n$ 种掩码即可枚举全部替换方案再用一次线性扫描把连续的被替换位合并成数字from typing import List class Solution: def generateAbbreviations(self, word: str) - List[str]: n len(word) res [] for mask in range(1 n): cur [] cnt 0 for i in range(n): if (mask i) 1: cnt 1 # 该位置被替换累计数字长度 else: if cnt: # 连续替换段结束写入数字 cur.append(str(cnt)) cnt 0 cur.append(word[i]) # 保留原字符 if cnt: cur.append(str(cnt)) res.append(.join(cur)) return res两种思路殊途同归回溯按「选择树」深度优先枚举位运算按「掩码空间」广度枚举但生成的有效缩写集合完全一致——因为合法缩写的约束不重叠、不相邻本质上等价于「一组不相邻的连续替换段」而连续段天然不会产生相邻数字。4. 从原理到实践本解法与仓库回溯体系的对应关系本题在 AlgoNote 中归类于「回溯」主题可对照仓库的 回溯算法理论章节 理解其方法论归属。该章节将回溯过程归纳为四步明确所有选择本题每一步的选择是「保留字符」或「开启一段数字替换」可用决策树完整刻画搜索空间明确终止条件本题终止条件是处理完所有字符index len(word)此时把current加入答案集——对应理论章节「递归到达指定深度时处理当前结果」将决策树转化为代码定义回溯函数参数index、current、is_prev_digit完整表达「当前状态」书写「选择 → 递归 → 恢复现场」主体明确终止处理约束即剪枝is_prev_digit的存在让本解法在搜索时就规避了相邻数字相当于在枚举过程中即时剪枝避免了生成后统一过滤的额外开销。理论章节中全排列、子集等经典例题与本解的对比也很有启发性子集问题如 78. 子集对每个元素做「选 / 不选」本题对每个位置做「保留 / 替换」二者共享同一棵 0-1 决策树骨架与全排列不同本题每个位置只会被访问一次index严格递增无需担心重复排列因此没有去重约束只有相邻性约束。5. 系列延展广义缩写主题在 AlgoNote 中的完整图谱「广义缩写」在 AlgoNote 题解库中是一个成体系的主题本题是其中最基础的「全量枚举」问题其余题目分别从「验证」「唯一性」「最短性」等角度考查同一套缩写规则推荐按以下顺序串联学习题目考查点与本题的关系0320. 列举单词的全部缩写本文回溯枚举全部合法缩写缩写规则的「生成」端0408. 有效单词缩写双指针验证给定缩写是否合法缩写规则的「验证」端反向检验相邻数字、前导零等非法形态0411. 最短独占单词缩写回溯 字典求不与词典冲突的最短缩写在生成基础上叠加「唯一性」约束0527. 单词缩写贪心 / 字典树为单词数组批量生成最短唯一缩写从单词级缩写的应用场景这些题目的标签与解法形态各异双指针、贪心、字典树、位运算、回溯但底层都围绕同一套「用数字替换连续字符、且替换段不可重叠相邻」的规则展开。理解本文的广义缩写生成逻辑是理解后续所有缩写类题目的共同前提。6. 小结LeetCode 0320「列举单词的全部缩写」是回溯算法在字符串枚举场景下的典型应用核心收获有三点状态设计is_prev_digit这类「历史状态」参数是保证解合法性的关键它把「相邻性约束」融入了搜索过程本身搜索结构「保留 / 替换」的二叉选择配合替换长度枚举完整覆盖 $2^n$ 种方案且不重不漏复杂度 $O(2^n \times n)$ 与数据范围$n \le 15$相匹配知识联动与 回溯算法理论章节、0408 有效单词缩写 等仓库文档形成「生成—验证—应用」的完整学习闭环。掌握本题后建议在本地运行代码验证word输出的 16 种缩写与示例完全一致再尝试abcde32 种结果以此巩固对决策树枚举与剪枝约束的理解。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 0046「全排列」回溯算法深度解析AlgoNote 算法通关手册LeetCode 0046「全排列」回溯算法深度解析 全排列Permutations是回溯算法最经典的入门问题也是算法面试教程文档知识库reth eth-wire 深度解析RLPx 与 Eth 协议的 Rust 实现、流式设计与版本演进reth eth wire 深度解析RLPx 与 Eth 协议的 Rust 实现、流式设计与版本演进 reth 的 eth wire 是节点参与以太坊 P2P教程文档知识库GutenbergWordPress 区块编辑器MenuItem 组件全解Props、可访问性语义与源码实现GutenbergWordPress 区块编辑器MenuItem 组件全解Props、可访问性语义与源码实现 本篇以 packages/component教程文档知识库上一篇终极游戏加速解决方案OpenSpeedy内存池如何突破动态分配瓶颈下一篇Cycle.js热重载与Vue 2集成在响应式应用中使用Vue 2创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考