🎪獨樹一格 只出現一次的單字 Uncommon Words from Two Sentences_LC #884

Drew Beamer on Unsplash

題目敘述 884. Uncommon Words from Two Sentences

給定兩個字串s1 和 s2，請找出uncommon words，以陣列的形式返回答案。

uncommon word的定義:

某個單字只在s1出現一次，沒有出現在s2；或者

某個單字只在s2出現一次，沒有出現在s1。

測試範例

Example 1:

Input: s1 = "this apple is sweet", s2 = "this apple is sour"

Output: ["sweet","sour"]

Explanation:

The word "sweet" appears only in s1, while the word "sour" appears only in s2.

Example 2:

Input: s1 = "apple apple", s2 = "banana"

Output: ["banana"]

約束條件

Constraints:

• 1 <= s1.length, s2.length <= 200

s1,s2 字串的長度都介於1~200之間。

• s1 and s2 consist of lowercase English letters and spaces.

s1,s2都只會有小寫英文字母和空白。

• s1 and s2 do not have leading or trailing spaces.

s1, s2頭尾都不會有多餘的空白。

• All the words in s1 and s2 are separated by a single space.

s1, s2內部所有單字都以一個空白作為間格。

演算法 字典統計次數

從題目uncommon word的定義可以知道，

要嘛這個單字出現在s1一次，s2零次；或者

這個單字出現在s1零次，s2一次。

可以推論知道，uncommon word的總共出現次數恰好為一次。

程式碼 字典統計次數

 class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        
        
        ## Counter() is Python built-in specialized dictionary
        # key: word
        # value: occurrence of word
        word_occ_1 = Counter( s1.split() )
        word_occ_2 = Counter( s2.split() )
        
        uncommon = []
        
        for word in (word_occ_1 | word_occ_2):
            
            # follow the difinition of "uncommon", given by description
            if word_occ_1[word] + word_occ_2[word] == 1:
                uncommon.append(word)
        
        return uncommon

複雜度分析

時間複雜度: O(m+n)

掃描每個單字，建立字典，所需時間為O(m) + O(n) = O(m + n)

空間複雜度: O(m+n)

掃描每個單字，建立字典，所需空間為O(m) + O(n) = O(m + n)

Reference

[1] Uncommon Words from Two Sentences - LeetCode