LeetCode 补充题 120. 保持顺序的单词去重
题目描述
给你一个只包含英文字母和空格的字符串
s，请删除重复的单词，只保留每个单词第一次出现时的相对顺序。返回用单个空格连接的结果，不保留首尾空格或连续空格。单词比较区分大小写；空串或全空格输入返回空字符串。
示例 1：
输入：
s = " java go java python go "
输出："java go python"
解释： 第一次出现顺序为 java、go、python，后续重复项删除。
示例 2：
输入：
s = "Java java Java"
输出："Java java"
解释： Java 与 java 视为两个不同单词。
提示：
- 大小写敏感。
- 空串或全空格输入返回空字符串。
题意分析
需要保留首次出现的单词，而不是删除所有出现重复的词。判重只关心此前是否出现，输出顺序则必须跟随从左到右的扫描顺序，不能直接遍历无序集合生成结果。
解法：集合判重与顺序输出
核心思路
[!blue]
将连续空格作为分隔，逐个取得非空单词。
seen保存已经输出的单词，out按首次出现顺序保存结果；若当前词不在集合中，就同时加入两者，否则跳过。扫描任意前缀后，
out恰好包含该前缀所有不同单词的首次出现，因此扫描结束便满足去重与保序要求。比较时不转换大小写，让Java与java保持不同。最后用单个空格连接
out，自然消除首尾和连续空格。Java 显式跳过空词，Go 的Fields不产生空词，空串及全空格输入都返回空字符串。
解题步骤
- 按题目约定分词，并跳过空词。
- 集合只用于判重，首次见到的词追加到结果。
- 用单个空格连接结果。
代码实现
class Solution {
public String uniqueWords(String s) {
Set<String> seen = new HashSet<>();
List<String> out = new ArrayList<>();
for (String word : s.trim().split(" +")) {
if (!word.isEmpty() && seen.add(word)) {
out.add(word);
}
}
return String.join(" ", out);
}
}
import "strings"
func uniqueWords(s string) string {
seen := map[string]bool{}
out := []string{}
for _, word := range strings.Fields(s) {
if !seen[word] {
seen[word] = true
out = append(out, word)
}
}
return strings.Join(out, " ")
}
复杂度分析
- 时间复杂度：期望 $O(n)$。
- 空间复杂度：额外空间 $O(n)$，n 为字符串长度。
关键点总结
[!green]
去重与输出顺序是两个职责：集合负责是否出现过，扫描和追加顺序负责稳定性。
易错点总结
[!yellow]
不按字典序重排，也不删除所有重复词；第一次出现的那一份需要保留。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 387. 字符串中的第一个唯一字符 | 简单 | 两题都利用原出现顺序；387 需先统计完整频次，筛选只出现一次的字符，本题仅用已见集合，保留每种单词首次出现，不要求总次数为一。 |
| 217. 存在重复元素 | 简单 | 两题都用已见集合判断当前值是否重复；本题对首次出现的单词追加输出，该题首次发现重复即可结束。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！