物以類聚 尋找共同的字元_字典應用_Leetcode #1002

Hans-Jurgen Mager on Unsplash

題目敘述

給定一個字串陣列，請把它們所共有的字元伴隨著出現次數輸出。

例如:每個字串都有兩個a，三個b，則輸出["a","a","b","b","b"]

測試範例

Example 1:

Input: words = ["bella","label","roller"]
Output: ["e","l","l"]

Example 2:

Input: words = ["cool","lock","cook"]
Output: ["c","o"]

約束條件

Constraints:

• 1 <= words.length <= 100

每個單字的長度介於1~100之間。

• 1 <= words[i].length <= 100

輸入陣列有1~100個單字。

• words[i] consists of lowercase English letters.

每個單字只會有小寫英文字母。

觀察

共有的字元怎麼找?

其實就是交集的部分。

每個單字取交集，得到的就是共同的字元。

如果再考慮出現次數，可以使用字典統計每個字元的出現次數，再逐一對每個單字產生的字典取交集，得到的就是共同的字元伴隨著共有的出現次數。

演算法 字典統計出現次數+字典取交集

承接觀察點的思考。

先針對每個單字建立字典，統計每個字元的出現次數。

接著對每個字典取交集，得到的就是共同的字元，伴隨著共有的出現次數。

程式碼 字典統計出現次數+字典取交集

from collections import Counter
from functools import reduce

class Solution:
    def commonChars(self, A: List[str]) -> List[str]:
        
        # Base case:
        A[0] = Counter(A[0])
        
        # functor to evaluate intersection of Counter
        func = lambda x, y: x & Counter(y)
        
        # update dictionary for common characters by itersection of Counter
        str_occ_dict = reduce( func, A)
        
        return list( str_occ_dict.elements() )

複雜度分析

時間複雜度: O(n)

掃描過每個單字，統計每個英文字母的出現次數，接著取交集。

空間複雜度: O(n)

需要建立字典，題目已經說都是小寫英文字母，最多只會占用O(26*n) = O(n)的空間。

關鍵知識點

集合(Set): 檢查元素是否存在。

字典(HashMap, Dictionary): 統計元素的出現次數。

以本題來說，字典比集合更符合需求，是比較直覺也比較適合的資料結構。

Reference

[1] Find Common Characters - LeetCode