LeetCode如何实现两句话中的不常见单词

问题描述

给定两个句子sentence1和sentence2，需要找出在这两个句子中只出现一次的单词。这些只出现一次的单词被称为不常见单词（Uncommon Words）。

解题思路

解决这个问题可以使用哈希表。首先，使用哈希表记录sentence1中每个单词的出现次数。然后再遍历sentence2，对于每个单词，在哈希表中查找是否已经出现过。根据出现次数判断单词是否为不常见单词。

代码实现

from collections import defaultdict

def uncommon_words(sentence1, sentence2):
    words_count = defaultdict(int)
    uncommon_words = []
    
    # 记录sentence1中每个单词的出现次数
    for word in sentence1.split():
        words_count[word] += 1
    
    # 遍历sentence2，判断每个单词是否为不常见单词
    for word in sentence2.split():
        if words_count[word] == 0:
            uncommon_words.append(word)
        else:
            words_count[word] -= 1
    
    # 遍历哈希表，找出只出现一次的单词
    for word, count in words_count.items():
        if count == 1:
            uncommon_words.append(word)
            
    return uncommon_words

复杂度分析

假设sentence1和sentence2的长度分别为n和m，那么时间复杂度为O(n+m)，空间复杂度为O(n)。