当前位置：首页 > news >正文

Swift 解 LeetCode 320：一行单词有多少种缩写可能？用回溯找全解

news 2025/7/8 12:12:40

在这里插入图片描述

文章目录

- 摘要
- 描述
- - 例子
- 题解答案
- 题解代码分析（Swift 实现）
- 题解代码详解
- - 每个位置的两种选择
  - 举个例子：word
- 示例测试及结果
- 时间复杂度
- 空间复杂度
- 总结

摘要

如果你用过 Google Docs 或翻译软件，应该见过“缩写建议”的功能：比如 international 会被缩写成 i10l，这个“只保留首尾字母，其余用数字代替”的方式其实就是一种泛化缩写（Generalized Abbreviation）。

LeetCode 320 要求我们列出一个单词的所有可能缩写方式。表面上是组合题，实则考你如何用递归 + 回溯 + 状态转移去遍历所有方案。

这篇文章用 Swift 带你一步步实现这个功能，并配上可运行的 Demo 和逻辑解析。适合初学者理解回溯思想，也适合面试前突击一波组合生成问题。

描述

给定一个单词 word，返回它的所有可能缩写方式，规则是：

你可以用数字代替连续的一段字符，表示它们被“省略”；
每个字符都可以选择保留 or 被缩写为某段数字。

例子

输入： "word"
输出（部分）：

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "w1r1", "1o1d", "3d", "4", ...]

共计 2⁴ = 16 种可能缩写（因为每个字符都有两个选择：保留或缩写）。

题解答案

这类问题有个固定套路：

每一位都有“做 or 不做”的选择；
把这个选择过程用 递归（或 DFS） 表达出来；
用一个变量 count 来累积连续被略去的字符数量；
当递归结束时，把路径拼起来加入结果集。

所以这题本质上是一个经典的回溯遍历全排列问题，加上了缩写计数规则。

题解代码分析（Swift 实现）

func generateAbbreviations(_ word: String) -> [String] {var result = [String]()let chars = Array(word)func dfs(_ pos: Int, _ cur: String, _ count: Int) {if pos == chars.count {var abbr = curif count > 0 {abbr += String(count)}result.append(abbr)return}// 选：保留当前字符var keep = curif count > 0 {keep += String(count)}keep += String(chars[pos])dfs(pos + 1, keep, 0)// 不选：跳过当前字符，缩写计数 +1dfs(pos + 1, cur, count + 1)}dfs(0, "", 0)return result
}

题解代码详解

这段代码里，核心是递归函数 dfs(pos, cur, count)：

pos：当前递归到第几个字母；
cur：当前拼接出来的缩写字符串；
count：当前累计省略（略去）的字符数。

每个位置的两种选择

保留这个字符：
- 如果之前略去了一段，要先把 count 加入字符串；
- 然后加上当前字符；
- 然后继续递归到下一位。
省略这个字符：
- 不修改字符串，只让 count + 1；
- 继续递归。

举个例子：word

从 word 开始：

w → o → r → d
每个字母有保留或略过两种路径

最终会得到如下 16 个组合：

["word", "wor1", "wo1d", "wo2", "w1rd", "w1r1", "w2d", "w3","1ord", "1or1", "1o1d", "1o2", "2rd", "2r1", "3d", "4"]

示例测试及结果

let result = generateAbbreviations("word")
print(result.sorted())// 输出（排序后）：
["1o1d", "1o2", "1or1", "1ord", "2r1", "2rd","3d", "4", "w1r1", "w1rd", "w2d", "w3","wo1d", "wo2", "wor1", "word"
]