916. Word Subsets | Swift | July LeetCoding Challenge 2022

題目

2022/7/30 ，July LeetCoding Challenge 2022 的題目

• 題目： https://leetcode.com/problems/word-subsets/
• 難度： Medium

思路

Hash Map

因為不需要顧及字元排列順序，所以可以先幫他們做字元出現次數 hash maps ，舉例來說

facebook

可以轉換成

["f": 1, "a": 1, "c": 1, "e": 1, "b": 1, "o": 2, "k": 1]

找出有 subsets 的字串

以原始的資料結構會讓時間複雜度成為指數複雜度。

不過根據題意，要滿足 word2 所有的元素後才能算是符合。

以此就可以將 word2 的 hashmaps 簡化成每個字元只取出現最多次的值，這樣 words 就從多個 hashmap 簡化到剩下一個。

程式碼

class Solution {
    func wordSubsets(_ words1: [String], _ words2: [String]) -> [String] {
        var result = [String]()

        // MARK: - 統整出 word2 的 hash map

        var words2Map = [Character: Int]()
        for word in words2 {
            // 1. 計算出每個字元出現的次數
            var map = [Character: Int]()
            for character in word {
                map[character, default: 0] += 1
            }

            // 2. 如果有出現最大值，紀錄到 words2Map
            for (character, value) in map {
                words2Map[character] = max(words2Map[character] ?? 0, value)
            }
        }

        // MARK: - 走訪 words1 的每一個元素。來和 words2Map 比較

        word1: for word in words1 {
            // 1. 計算出每個字元出現的次數
            var map = [Character: Int]()
            for character in word {
                map[character, default: 0] += 1
            }

            // 2. 和 words2Map 比較
            for (character, value) in words2Map {
                if (map[character] ?? 0) < value {
                    continue word1
                }
            }
            result.append(word)
        }
        
        return result
    }
}

分析

• n - words1 中所有的字元數
• m - words2 中所有的字元數

時間複雜度

O(n + m)

兩個陣列都只有以線性的方式走過

空間複雜度

O(n + m)

最壞情況下會為每一個字元都使用到空間