算法题 两句话中的不常见单词

两句话中的不常见单词

问题描述

句子是一串由空格分隔的单词。给定两个句子s1和s2，返回所有不常见单词的列表。

不常见单词：在两个句子中总共只出现一次，且至少出现在一个句子中的单词。

可以按任意顺序返回答案。

示例：

输入:s1="this apple is sweet",s2="this apple is sour"输出:["sweet","sour"]输入:s1="apple apple",s2="banana"输出:["banana"]

算法思路

哈希表统计频次：

1. 核心思想：
   • 将两个句子合并，统计每个单词的出现频次
   • 出现频次为 1 的单词就是不常见单词

代码实现

方法一：哈希表统计

importjava.util.*;classSolution{/** * 找出两句话中的不常见单词 * * @param s1 第一个句子 * @param s2 第二个句子 * @return 所有不常见单词的列表 * * 算法思路： * 1. 将两个句子合并统计单词频次 * 2. 频次为1的单词即为不常见单词 */publicString[]uncommonFromSentences(Strings1,Strings2){// 使用哈希表统计单词频次Map<String,Integer>wordCount=newHashMap<>();// 处理第一个句子String[]words1=s1.split(" ");for(Stringword:words1){wordCount.put(word,wordCount.getOrDefault(word,0)+1);}// 处理第二个句子String[]words2=s2.split(" ");for(Stringword:words2){wordCount.put(word,wordCount.getOrDefault(word,0)+1);}// 收集频次为1的单词List<String>result=newArrayList<>();for(Map.Entry<String,Integer>entry:wordCount.entrySet()){if(entry.getValue()==1){result.add(entry.getKey());}}// 转换为数组返回returnresult.toArray(newString[0]);}}

方法二：使用Stream

importjava.util.*;importjava.util.stream.*;classSolution{/** * 使用Stream */publicString[]uncommonFromSentences(Strings1,Strings2){// 合并两个句子的所有单词String[]allWords=(s1+" "+s2).split(" ");// 统计频次并过滤频次为1的单词Map<String,Long>wordCount=Arrays.stream(allWords).collect(Collectors.groupingBy(word->word,Collectors.counting()));// 返回频次为1的单词数组returnwordCount.entrySet().stream().filter(entry->entry.getValue()==1).map(Map.Entry::getKey).toArray(String[]::new);}}

算法分析

• 时间复杂度：O(m + n)

  • m 和 n 分别是两个句子的长度
  • 分割字符串：O(m + n)
  • 哈希表操作：每个单词 O(1)，总共 O(m + n)
  • 构建结果：O(k)，其中 k 是不同单词的数量

• 空间复杂度：O(m + n)

  • 哈希表存储所有不同单词：O(m + n)
  • 结果数组：O(k) ≤ O(m + n)

算法过程

1：s1 = “this apple is sweet”, s2 = “this apple is sour”

单词统计：

s1单词: ["this", "apple", "is", "sweet"] s2单词: ["this", "apple", "is", "sour"] 哈希表统计: - "this": 2 - "apple": 2 - "is": 2 - "sweet": 1 - "sour": 1 频次为1的单词: ["sweet", "sour"]

2：s1 = “apple apple”, s2 = “banana”

单词统计：

s1单词: ["apple", "apple"] s2单词: ["banana"] 哈希表统计: - "apple": 2 - "banana": 1 频次为1的单词: ["banana"]

3：s1 = “abcd def abcd”, s2 = “def mnop mnop”

单词统计：

哈希表统计: - "abcd": 2 - "def": 2 - "mnop": 2 频次为1的单词: [] (空数组)

测试用例

importjava.util.*;publicclassTest{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例Strings1_1="this apple is sweet";Strings2_1="this apple is sour";String[]result1=solution.uncommonFromSentences(s1_1,s2_1);System.out.println("Test 1: "+Arrays.toString(result1));// [sweet, sour]// 测试用例2：重复单词Strings1_2="apple apple";Strings2_2="banana";String[]result2=solution.uncommonFromSentences(s1_2,s2_2);System.out.println("Test 2: "+Arrays.toString(result2));// [banana]// 测试用例3：无结果Strings1_3="abcd def abcd";Strings2_3="def mnop mnop";String[]result3=solution.uncommonFromSentences(s1_3,s2_3);System.out.println("Test 3: "+Arrays.toString(result3));// []// 测试用例4：单个单词Strings1_4="hello";Strings2_4="world";String[]result4=solution.uncommonFromSentences(s1_4,s2_4);System.out.println("Test 4: "+Arrays.toString(result4));// [hello, world]// 测试用例5：一个句子为空Strings1_5="";Strings2_5="hello world";String[]result5=solution.uncommonFromSentences(s1_5,s2_5);System.out.println("Test 5: "+Arrays.toString(result5));// [hello, world]// 测试用例6：两个句子相同Strings1_6="same words here";Strings2_6="same words here";String[]result6=solution.uncommonFromSentences(s1_6,s2_6);System.out.println("Test 6: "+Arrays.toString(result6));// []// 测试用例7：包含数字和特殊字符Strings1_7="hello123 world!";Strings2_7="hello123 test";String[]result7=solution.uncommonFromSentences(s1_7,s2_7);System.out.println("Test 7: "+Arrays.toString(result7));// [world!, test]// 测试用例8：大量重复Strings1_8="a a a a a";Strings2_8="b b b b b";String[]result8=solution.uncommonFromSentences(s1_8,s2_8);System.out.println("Test 8: "+Arrays.toString(result8));// []// 测试用例9：一个单词在两个句子中各出现一次Strings1_9="unique";Strings2_9="unique";String[]result9=solution.uncommonFromSentences(s1_9,s2_9);System.out.println("Test 9: "+Arrays.toString(result9));// []// 测试用例10：混合大小写Strings1_10="Hello hello";Strings2_10="WORLD world";String[]result10=solution.uncommonFromSentences(s1_10,s2_10);System.out.println("Test 10: "+Arrays.toString(result10));// [Hello, hello, WORLD, world]}}

关键点

1. 问题：

   • 不常见单词 = 在两个句子中总共出现1次
   • 不是"在各自句子中只出现1次"，而是"在合并后只出现1次"

2. 字符串分割：

   • 使用split(" ")处理空格分隔

常见问题

1. 为什么不用Set？
   • Set只能判断存在性，无法统计频次
   • 需要知道单词出现了多少次，而不仅仅是是否出现