LeetCode 补充题 182. 数字字符串的所有解码结果
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 91. 解码方法
:::
给定非空数字字符串，按
1→A、2→B、…、26→Z解码，返回所有解码字符串。
0不能单独解码，两位编码不能有前导零。结果顺序不限。
示例 1：
输入：
s = "121"
输出：["ABA","AU","LA"]
解释： 分别对应1/2/1、1/21、12/1三种合法分割。
示例 2：
输入：
s = "10"
输出：["J"]
解释：10可以整体映射为J，0不能单独解码。
示例 3：
输入：
s = "06"
输出：[]
解释：06含前导零，且首位0不能单独解码。
提示：
- 输入为非空数字字符串。
- 编码范围为
1…26。 -
0不能单独解码，两位编码不能有前导零。 - 输出顺序不限。
题意分析
每个字母编码只有一位或两位，所以从当前数字位置出发，所有合法答案都可由这两种长度的选择产生。题目要求具体字符串，需保留递归路径，而不能只用计数状态返回数量。
解法：按一位或两位数字回溯全部解码
核心思路
[!blue]
i表示下一个尚未消费的数字位置，path是此前分段得到的字母串。到达字符串末尾时说明全部数字均被合法覆盖，保存当前字符串；若当前数字是 0，则没有任何合法编码能从这里开始，立即终止该分支。非零时总可尝试一位编码；若还有下一位，再组成两位数，只有不超过 26 才递归。因为已排除首位 0，两位数自然至少为 10，既不会接受前导零，也能把 10、20 作为整体处理。
每次递归前记录路径长度，返回后恢复，再尝试另一分支。每种合法分段被枚举一次，且字母与编码一一对应，不需要额外结果去重。
解题步骤
- 到字符串末尾时保存当前字母路径。
- 当前位置为 0 时停止该分支，否则先尝试一位解码。
- 再尝试合法的两位编码，每次递归返回后恢复路径长度。
代码实现
class Solution {
public List<String> decodeAll(String s) {
List<String> out = new ArrayList<>();
if (!s.isEmpty()) {
dfs(s, 0, new StringBuilder(), out);
}
return out;
}
private void dfs(String s, int i, StringBuilder path, List<String> out) {
if (i == s.length()) {
out.add(path.toString());
return;
}
if (s.charAt(i) == '0') {
return;
}
int size = path.length();
path.append((char) ('A' + s.charAt(i) - '1'));
dfs(s, i + 1, path, out);
path.setLength(size);
if (i + 1 < s.length()) {
int value = (s.charAt(i) - '0') * 10 + s.charAt(i + 1) - '0';
if (value <= 26) {
path.append((char) ('A' + value - 1));
dfs(s, i + 2, path, out);
path.setLength(size);
}
}
}
}
func decodeAll(s string) []string {
out := []string{}
path := []byte{}
var dfs func(int)
dfs = func(i int) {
if i == len(s) {
out = append(out, string(path))
return
}
if s[i] == '0' {
return
}
size := len(path)
path = append(path, 'A'+s[i]-'1')
dfs(i + 1)
path = path[:size]
if i+1 < len(s) {
value := int(s[i]-'0')*10 + int(s[i+1]-'0')
if value <= 26 {
path = append(path, byte('A'+value-1))
dfs(i + 2)
path = path[:size]
}
}
}
if len(s) > 0 {
dfs(0)
}
return out
}
复杂度分析
- 时间复杂度：最坏 $O(n\cdot 2^n)$。
- 空间复杂度：递归与路径空间 $O(n)$，结果空间另计。
关键点总结
[!green]
转移是否合法与计数题一致；枚举需要维护具体路径，输出规模可能指数增长。
易错点总结
[!yellow]
每次返回前恢复路径长度；计数动态规划不能直接代替方案枚举。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 91. 解码方法 | 中等 | 复用 1 到 26 的合法转移，但本题要保存字母路径并枚举全部结果，不能只返回计数。 |
| 93. 复原 IP 地址 | 中等 | 同样枚举数字片段并处理前导零，原题固定四段且限制到 255，本题每段一位或两位。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！