🔗 🟢 884. Uncommon Words from Two Sentences 1259

tags: Weekly Contest 97 字串(String) 雜湊表(Hash Table) 計數(Counting)

題意

一個 句子(Sentence) 是一串 單字(Word) 組成的字串，每個單字間以空格分隔，且每個單字只含有小寫字母。

給定兩個句子 s1s1 和 s2s2 。如果一個單字在其中一個句子中恰好出現一次，在另一個句子中卻 沒有出現 ，那麼這個單字被認為是 不常見的(uncommon) 。

請返回所有不常見單字的列表，可以以 任意順序 返回 。

思路：雜湊表 + 分組循環

最直接的寫法只需要分別維護兩個句子中的單字出現次數 cnt1cnt1 和 cnt2cnt2，然後按照題意模擬，找出那些只出現一次的單字且不在另一個句子中出現的單字即可。

至於將句子分割成單字，可以使用 Python 的 split() 方法，或是 C++ 的 istringstream 來實現。但我在 C++ 中選擇使用分組循環的方式來處理，將不同的單字視為一組，令每組的第一個字元下標為 i=sti = st，之後持續遍歷直到遇到空格為止，這樣就可以將一個單字從句子中分割出來。

此外，「只出現一次的單字且不在另一個句子中出現」的單字，等同於「在兩個句子中出現次數為 11 」的單字，因此其實只需要維護一個雜湊表 cntcnt 即可。

複雜度分析

  • 時間複雜度：O(n1+n2)O(n_1 + n_2)，其中 n1n_1 和 n2n_2 分別是 s1s1 和 s2s2 的長度。
    • 將句子分割成單字，並統計每個單字的出現次數，需要 O(n1+n2)O(n_1 + n_2) 的時間。
    • 遍歷雜湊表，找出那些在其中一個句子中出現了一次，而在另一個句子中沒有出現的單字，時間複雜度為 O(m1+m2)O(m_1 + m_2)，其中 m1m_1 和 m2m_2 是兩個單字列表的長度。
    • 但由於 m1m_1 和 m2m_2 的總和最多為 n1+n2n_1 + n_2，因此總時間複雜度為 O(n1+n2)O(n_1 + n_2)。
  • 空間複雜度：O(n1+n2)O(n_1 + n_2)。
    • 需要額外的空間來存儲雜湊表 cntcnt，其空間需求為 O(n1+n2)O(n_1 + n_2)。
    • 答案列表 ansans 的空間需求在最壞情況下也為 O(n1+n2)O(n_1 + n_2)，即所有單字都不常見。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:
        # cnt = Counter(s1.split() + s2.split())
        # return [w for w, v in cnt.items() if v == 1]
        words1, words2 = s1.split(), s2.split()
        cnt1, cnt2 = Counter(words1), Counter(words2)
        ans = []
        for word in words1:
            if cnt1[word] == 1 and word not in words2:
                ans.append(word)
        for word in words2:
            if cnt2[word] == 1 and word not in words1:
                ans.append(word)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<string> uncommonFromSentences(string s1, string s2) {
        unordered_map<string, int> cnt;

        function<void(string)> insert = [&](string s) {
            int n = s.size(), i = 0, st = 0;
            while (i < n) {
                st = i;
                while (i < n && s[i] != ' ') i++;
                cnt[s.substr(st, i - st)]++;
                i++; // skip space
            }
        };

        insert(s1);
        insert(s2);
        
        vector<string> ans;
        for (auto &[word, v] : cnt) {
            if (v == 1) {
                ans.push_back(word);
            }
        }
        return ans;
    }
};

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

(1girl, solo), long hair, (black eyes), looking at viewer, (standing), full body, black hair, school uniform, short sleeves, pleated skirt, skirt, shirt, (green top, green shirt), black bottom, (black skirt), serafuku, socks, looking back, indoors, sailor collar, black footwear, window, white socks, hallway,

A girl in a green shirt and black pleated skirt standing, in a long school hallway, windows and doors on both sides, bright natural light coming through the windows, serene atmosphere, looking back at the camera,

復健中。