LeetCode 补充题 140. 字符串的不同子序列枚举
题目描述
牛客原题： ✅ 补充题 140. 字符串的不同子序列枚举
给定字符串
s，返回它的全部不同子序列，包含空串。可以删去任意位置的字符，但必须保留剩余字符的相对顺序。相同字符串结果只返回一次，输出顺序不限。
示例 1：
输入：
s = "aab"
输出：["","a","aa","b","ab","aab"]
解释： 结果包含空串；从不同位置选出相同的"a"或"ab"时，只保留一份。顺序不限。
提示：
- 子序列保留字符相对顺序。
- 包含空串。
- 相同结果只保留一次。
- 输出顺序不限。
题意分析
对每个位置都有选或不选两种决策，但不同下标可能得到相同字符串，本题按结果内容去重。可以逐个读取字符，维护当前前缀的全部不同子序列，用集合合并重复结果。
解法：冻结上一轮结果后扩展并去重
核心思路
[!blue]
初始前缀为空，唯一子序列是空串。读到新码点时，不选择它的结果就是原集合；选择它的结果则是给每个旧子序列末尾追加当前码点。这两类覆盖新前缀的全部子序列。
列表保存可遍历的结果，集合检查内容是否已经出现。必须在本轮开始时保存列表旧长度，只扩展这部分结果；若连新追加项也继续扩展，就会在同一轮重复使用当前位置。
集合中已有的字符串无需重复保存，因为后续字符只与字符串内容有关，不依赖它由哪些下标形成。按码点追加保证多字节字符完整，空输入保留最初的空串。
解题步骤
- 以空串作为初始唯一结果。
- 读到一个码点时先保存本轮之前的结果数量。
- 只给这些旧结果追加当前码点，集合判重后加入新结果。
代码实现
class Solution {
public List<String> subsequences(String s) {
List<String> result = new ArrayList<>();
Set<String> seen = new HashSet<>();
result.add("");
seen.add("");
for (int c : s.codePoints().toArray()) {
String suffix = new String(Character.toChars(c));
int size = result.size();
for (int i = 0; i < size; i++) {
String next = result.get(i) + suffix;
if (seen.add(next)) {
result.add(next);
}
}
}
return result;
}
}
func subsequences(s string) []string {
result := []string{
"",
}
seen := map[string]bool{"": true}
for _, c := range s {
size := len(result)
for i := 0; i < size; i++ {
next := result[i] + string(c)
if !seen[next] {
seen[next] = true
result = append(result, next)
}
}
}
return result
}
复杂度分析
- 时间复杂度：$O(n\cdot 2^n)$，包含字符串复制。
- 空间复杂度：存储空间 $O(n\cdot 2^n)$，包含结果空间。
最多2^n个结果。
关键点总结
[!green]
冻结旧长度保证同一轮不会反复使用当前字符；结果集合控制的是字符串内容，而非选择的下标。
易错点总结
[!yellow]
子序列允许不连续；集合去重不能漏掉空串；不能一边追加结果一边无限扩展本轮迭代范围。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 78. 子集 | 中等 | 子集按下标选择，本题还需把不同下标生成的相同字符串去重。 |
| 940. 不同的子序列 II | 困难 | 同样按内容区分不同子序列，原题只计数并消除重复贡献，本题必须实际输出每个字符串。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！