題目

解題概念

  • 此題簡單來說，就是要依照 words2 的所有字串，回傳對照 words1 的所有 Universal Set 字串
    • Subset (子集) 定義 : 若 b 字串的所有字母都有出現在 a 字串中(包含重複)</font，則稱 b 為 a 的一個 Subset (子集)
    • Universal Set (全集) 定義 : 若 words2 中的所有 b 字串都是 words1 中任一 a 字串的 Subset，則稱 a 為 Universal Set
  • 目標函式 : wordSubsets(words1, words2)
    • Input : words1: List[str]、words2: List[str]
    • Output : List[str]
  • 而實際執行上，有兩種以下解法

Method 1 : 直觀寫法

  • 解題概念 :
    1. 用雙重 for 迴圈比較 word1 與 word2 中的字串
    2. 用函數比較兩個字串，其中用26格的陣列去存兩個字串的字母分布(a → 0、z → 25)
  • 實際程式碼 : 
    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    def wordSubsets(self, words1, words2):
        res = [] # 存結果
        # 針對所有 words1 與 words2 的字串
        for word in words1 : 

            flag = 0 # 看 word 是否為 Universal Set
            
            for target in words2 :
                if not self.match(word, target) : # 比較 word 與 target

                    # 若有配對失敗，則直接回傳失敗
                    flag = 1
                    break
                    
            if flag == 0 : 
                res.append(word)

        return res

    # 比較 word 與 target
    def match(self, word, target) :  
        
        # 建立陣列存字母的分布
        w_map = [0] * 26
        t_map = [0] * 26

        # 存兩個字串的分布狀況  
        for w in word : 
            w_map[ord(w)-ord('a')] +=1
        for t in target : 
            t_map[ord(t)-ord('a')] +=1
        
        # 若 target 有不同於 word 的字母，則直接回傳 False
        for i in range(26):
            if t_map[i] > w_map[i] : 
                return False
        return True
  • 問題 :
    :::danger
    Runtime Error
    :::

Method 2 : 單迴圈寫法

  • 解題概念 :
    1. 先將 words2 所有字串的字母分布用 for 迴圈，存入 freq 陣列中
      • 可以直接合併所有字串的分布，因為可以把所有字串視為整個字串
    2. 用單一 for 迴圈比較 word1 與 freq，其中用26格的陣列去存兩個字串的字母分布(a → 0、z → 25)
  • 實際程式碼 : 
    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
    28
    29
    30
    31
    def wordSubsets(self, words1, words2):

        freq = [0] * 26 # 儲存 words2 所有字串的字母分布

        # 針對 words2 做處理
        for x in words2 : 
            temp = [0] * 26
            for y in x : 
                temp[ord(y) - ord('a')] += 1
                freq[ord(y) - ord('a')] = max(freq[ord(y) - ord('a')], temp[ord(y) - ord('a')])
                
        res = []
        # 接著用 words1 中的字串與 freq 做比較
        for x in words1:
            temp = [0] * 26

            # 先找出 words1 所有字串的字母分布
            for y in x :
                temp[ord(y) - ord('a')] += 1

            flag = 0
            for i in range(26) : 
                # 若 freq 有不同於 temp 的字母，則直接回傳 False
                if freq[i] > temp[i] : 
                    flag = 0
                    break
            
            if flag == 1:
                res.append(x)
                
        return res