Easy

题目描述

句子是一个由单个空格分隔的单词字符串，其中每个单词仅由小写字母组成。

如果一个单词在其中一个句子中恰好出现一次，而在另一个句子中不出现，那么这个单词就是不常见的。

给定两个句子 s1 和 s2，返回所有不常见单词的列表。你可以按任意顺序返回答案。

示例 1:

输入: s1 = "this apple is sweet", s2 = "this apple is sour"
输出: ["sweet","sour"]
解释: 单词 "sweet" 只在 s1 中出现，而单词 "sour" 只在 s2 中出现。

示例 2:

输入: s1 = "apple apple", s2 = "banana"
输出: ["banana"]

提示:

  • 1 <= s1.length, s2.length <= 200
  • s1 和 s2 由小写英文字母和空格组成
  • s1 和 s2 不含前导或尾随空格
  • s1 和 s2 中的所有单词都由单个空格分隔

解题思路

解题思路

这道题要求找出两句话中的不常见单词，即在整个语料库中只出现一次的单词。

核心观察

不常见单词的定义可以简化为：在两个句子合并后，出现次数恰好为1的单词。

这是因为：

  • 如果一个单词在某个句子中出现多次，它就不是不常见的
  • 如果一个单词在两个句子中都出现，它也不是不常见的
  • 只有在合并后的语料库中出现恰好1次的单词才是不常见的

算法步骤

  1. 合并两个句子：将s1和s2用空格连接
  2. 统计词频：使用哈希表记录每个单词的出现次数
  3. 筛选结果：找出出现次数为1的单词

这种方法比分别统计两个句子的词频再比较更加简洁高效。

推荐解法：直接统计合并句子的词频，时间复杂度O(n)，空间复杂度O(n)。

代码实现

class Solution {
public:
    vector<string> uncommonFromSentences(string s1, string s2) {
        unordered_map<string, int> count;
        string combined = s1 + " " + s2;
        
        istringstream iss(combined);
        string word;
        while (iss >> word) {
            count[word]++;
        }
        
        vector<string> result;
        for (auto& p : count) {
            if (p.second == 1) {
                result.push_back(p.first);
            }
        }
        
        return result;
    }
};

class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        from collections import Counter
        
        combined = s1 + " " + s2
        count = Counter(combined.split())
        
        return [word for word, freq in count.items() if freq == 1]

public class Solution {
    public string[] UncommonFromSentences(string s1, string s2) {
        var count = new Dictionary<string, int>();
        string combined = s1 + " " + s2;
        string[] words = combined.Split(' ');
        
        foreach (string word in words) {
            if (count.ContainsKey(word)) {
                count[word]++;
            } else {
                count[word] = 1;
            }
        }
        
        var result = new List<string>();
        foreach (var pair in count) {
            if (pair.Value == 1) {
                result.Add(pair.Key);
            }
        }
        
        return result.ToArray();
    }
}

/**
 * @param {string} s1
 * @param {string} s2
 * @return {string[]}
 */
var uncommonFromSentences = function(s1, s2) {
    const wordCount = new Map();
    
    const words = (s1 + " " + s2).split(" ");
    
    for (const word of words) {
        wordCount.set(word, (wordCount.get(word) || 0) + 1);
    }
    
    const result = [];
    for (const [word, count] of wordCount) {
        if (count === 1) {
            result.push(word);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)n为两个句子的总长度，需要遍历所有字符进行分割和统计
空间复杂度O(k)k为不同单词的数量，用于存储哈希表和结果数组

相关题目