★ FEATURED ARTICLE 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), number100) t2 timeit.timeit(lambda: method2(s1, s2), number100) print(f基础实现: {t1:.4f}秒) print(fCounter实现: {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 ListString uncommonFromSentences(String s1, String s2) { MapString, Integer count new HashMap(); for (String word : (s1 s2).split( )) { count.put(word, count.getOrDefault(word, 0) 1); } ListString 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可以大幅简化代码在实际工程中这类词频统计问题非常常见。掌握这种基础算法模式对处理日志分析、用户行为分析等任务都有很大帮助。
阅读完成 · 觉得有帮助？
