1. 题目理解与需求分析
今天我们来拆解LeetCode第884题"Uncommon Words from Two Sentences"。这道题看似简单，但蕴含着不少值得深入探讨的编程技巧和算法思想。
题目给出两个句子s1和s2，要求找出在两个句子中只出现一次的单词（即不常见单词）。这里的"不常见"定义很明确：在合并后的所有单词中，出现次数恰好为1次的单词。
举个例子：
- 输入：s1 = "this apple is sweet", s2 = "this apple is sour"
- 输出：["sweet","sour"]
因为"this"和"apple"在两个句子中各出现两次，"is"也出现两次，只有"sweet"和"sour"各出现一次。
2. 解题思路与算法选择
2.1 暴力解法分析
最直观的想法可能是：
- 合并两个句子的所有单词
- 统计每个单词出现的频率
- 筛选出频率为1的单词
这种方法虽然可行，但效率不高，特别是当句子很长时。我们需要考虑更优的解法。
2.2 哈希表（字典）的应用
更高效的解法是使用哈希表（在Python中就是字典）来统计词频。具体步骤：
- 将两个句子合并成一个单词列表
- 遍历列表，用字典记录每个单词出现的次数
- 再次遍历字典，收集所有值为1的键
这种方法的时间复杂度是O(n)，空间复杂度也是O(n)，其中n是单词总数。
2.3 Python实现细节
在Python中，我们可以利用collections模块的Counter类来简化词频统计：
from collections import Counter def uncommonFromSentences(s1: str, s2: str) -> List[str]: words = s1.split() + s2.split() count = Counter(words) return [word for word in count if count[word] == 1]3. 代码实现与优化
3.1 基础实现
让我们先看一个基础实现：
def uncommonFromSentences(s1, s2): word_count = {} for word in s1.split(): word_count[word] = word_count.get(word, 0) + 1 for word in s2.split(): word_count[word] = word_count.get(word, 0) + 1 return [word for word in word_count if word_count[word] == 1]3.2 使用Counter优化
Python的collections.Counter可以大幅简化代码：
from collections import Counter def uncommonFromSentences(s1, s2): count = Counter(s1.split() + s2.split()) return [word for word in count if count[word] == 1]3.3 时间复杂度分析
两种实现方式的时间复杂度都是O(n)，其中n是单词总数。因为：
- 分割字符串：O(n)
- 统计词频：O(n)
- 筛选结果：O(n)
空间复杂度也是O(n)，因为需要存储词频字典。
4. 边界条件与异常处理
4.1 空输入处理
需要考虑以下几种特殊情况：
- 两个句子都为空
- 其中一个句子为空
- 句子只包含空格
def uncommonFromSentences(s1, s2): if not s1.strip() and not s2.strip(): return [] words = s1.split() + s2.split() if not words: return [] count = Counter(words) return [word for word in count if count[word] == 1]4.2 标点符号处理
题目没有明确说明标点符号的处理方式，但通常可以假设：
- 单词只包含字母
- 标点符号被视为分隔符
如果需要更严格的处理，可以使用正则表达式：
import re from collections import Counter def uncommonFromSentences(s1, s2): words = re.findall(r'\b\w+\b', s1) + re.findall(r'\b\w+\b', s2) count = Counter(words) return [word for word in count if count[word] == 1]5. 测试用例设计
5.1 常规测试用例
测试用例1： 输入：s1 = "this apple is sweet", s2 = "this apple is sour" 输出：["sweet","sour"] 测试用例2： 输入：s1 = "apple apple", s2 = "banana" 输出：["banana"]5.2 边界测试用例
测试用例3： 输入：s1 = "", s2 = "" 输出：[] 测试用例4： 输入：s1 = "hello", s2 = "hello" 输出：[] 测试用例5： 输入：s1 = "a b c", s2 = "d e f" 输出：["a","b","c","d","e","f"]5.3 特殊字符测试
测试用例6： 输入：s1 = "hello, world!", s2 = "world hello" 输出：[] # 假设标点被视为分隔符 测试用例7： 输入：s1 = "hello world", s2 = "hello-world" 输出：["hello", "world", "hello-world"] # 连字符处理6. 算法优化与变种
6.1 空间优化
如果内存受限，可以分步处理：
def uncommonFromSentences(s1, s2): count = {} for word in s1.split(): count[word] = count.get(word, 0) + 1 for word in s2.split(): count[word] = count.get(word, 0) + 1 return [word for word in count if count[word] == 1]6.2 并行处理
对于超大输入，可以考虑并行处理：
from multiprocessing import Pool from collections import Counter def count_words(sentence): return Counter(sentence.split()) def uncommonFromSentences(s1, s2): with Pool(2) as p: counts = p.map(count_words, [s1, s2]) total = sum(counts, Counter()) return [word for word in total if total[word] == 1]7. 实际应用场景
这类词频统计问题在实际中有广泛应用：
- 文本分析：找出文档中的独特词汇
- 日志分析：识别异常日志条目
- 数据清洗：发现数据集中的罕见值
- 自然语言处理：构建词汇表时的预处理
8. 常见错误与调试技巧
8.1 常见错误
- 忘记处理空输入
- 错误地分割字符串（如忽略多个空格）
- 大小写敏感问题（题目通常假设大小写敏感）
- 标点符号处理不当
8.2 调试技巧
- 打印中间结果：检查分割后的单词列表
- 检查词频字典：确认统计是否正确
- 单元测试：覆盖各种边界条件
- 使用assert语句验证假设
def uncommonFromSentences(s1, s2): words = s1.split() + s2.split() print("Split words:", words) # 调试输出 count = Counter(words) print("Word counts:", count) # 调试输出 result = [word for word in count if count[word] == 1] return result9. 性能对比与基准测试
让我们比较几种实现方式的性能：
import timeit from collections import Counter # 方法1：基础实现 def method1(s1, s2): word_count = {} for word in s1.split(): word_count[word] = word_count.get(word, 0) + 1 for word in s2.split(): word_count[word] = word_count.get(word, 0) + 1 return [word for word in word_count if word_count[word] == 1] # 方法2：使用Counter def method2(s1, s2): count = Counter(s1.split() + s2.split()) return [word for word in count if count[word] == 1] # 测试数据 s1 = "a b c " * 1000 s2 = "d e f " * 1000 # 性能测试 t1 = timeit.timeit(lambda: method1(s1, s2), number=100) t2 = timeit.timeit(lambda: method2(s1, s2), number=100) print(f"基础实现: {t1:.4f}秒") print(f"Counter实现: {t2:.4f}秒")通常Counter实现会更快，因为它是用C实现的优化版本。
10. 扩展思考与类似题目
10.1 类似题目
- LeetCode 819：最常见的单词
- LeetCode 692：前K个高频单词
- LeetCode 49：字母异位词分组
10.2 扩展思考
- 如果要求不区分大小写怎么办？
- 如果单词可能包含连字符或撇号怎么办？
- 如果输入是超长字符串（GB级别）如何处理？
- 如果要求实时处理单词流（stream）怎么办？
# 不区分大小写的解决方案 def uncommonFromSentences(s1, s2): words = (s1.lower().split() + s2.lower().split()) count = Counter(words) return [word for word in count if count[word] == 1]11. 多语言实现比较
11.1 Java实现
import java.util.*; public List<String> uncommonFromSentences(String s1, String s2) { Map<String, Integer> count = new HashMap<>(); for (String word : (s1 + " " + s2).split(" ")) { count.put(word, count.getOrDefault(word, 0) + 1); } List<String> result = new ArrayList<>(); for (String word : count.keySet()) { if (count.get(word) == 1) { result.add(word); } } return result; }11.2 JavaScript实现
function uncommonFromSentences(s1, s2) { const words = s1.split(' ').concat(s2.split(' ')); const count = {}; words.forEach(word => { count[word] = (count[word] || 0) + 1; }); return Object.keys(count).filter(word => count[word] === 1); }11.3 Go实现
func uncommonFromSentences(s1 string, s2 string) []string { words := append(strings.Fields(s1), strings.Fields(s2)...) count := make(map[string]int) for _, word := range words { count[word]++ } var result []string for word, cnt := range count { if cnt == 1 { result = append(result, word) } } return result }12. 总结与个人心得
这道题目虽然标注为简单，但涵盖了字符串处理、哈希表应用、边界条件处理等多个基础知识点。在实际编码中，我发现有几点特别重要：
- 理解题目要求：明确"不常见单词"的定义是关键
- 选择合适的数据结构：哈希表/字典是解决词频统计问题的利器
- 考虑边界条件：空输入、重复单词、特殊字符等
- 代码简洁性：合理使用语言特性（如Python的Counter）可以大幅简化代码
在实际工程中，这类词频统计问题非常常见。掌握这种基础算法模式，对处理日志分析、用户行为分析等任务都有很大帮助。
