单词子集

前言

广州某知名外包公司的笔试题，明明第一轮笔试做过题目了，技术面上来还是一道编程题，还得手写，麻了麻了~

一开始的思路方向是对的，但还有优化空间，在面试官的提示下把题目完成了。

题目

题目链接 (opens new window)

难度：中等

给你两个字符串数组 words1 和 words2。

现在，如果 b 中的每个字母都出现在 a 中，包括重复出现的字母，那么称字符串 b 是字符串 a 的 子集 。

例如，"wrr" 是 "warrior" 的子集，但不是 "world" 的子集。 如果对 words2 中的每一个单词 b，b 都是 a 的子集，那么我们称 words1 中的单词 a 是 通用单词 。

以数组形式返回 words1 中所有的通用单词。你可以按 任意顺序 返回答案。

示例 1：

输入：words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
输出：["facebook","google","leetcode"]
示例 2：

输入：words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
输出：["apple","google","leetcode"]
示例 3：

输入：words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","oo"]
输出：["facebook","google"]
示例 4：

输入：words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["lo","eo"]
输出：["google","leetcode"]
示例 5：

输入：words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["ec","oc","ceo"]
输出：["facebook","leetcode"]
 

提示：

1 <= words1.length, words2.length <= 10^4
1 <= words1[i].length, words2[i].length <= 10
words1[i] 和 words2[i] 仅由小写英文字母组成
words1 中的所有字符串 互不相同

看着还是挺绕的，特别是在面试的过程中有些许紧张，导致一开始没看懂"wrr" 是 "warrior" 的子集，但不是 "world" 的子集。

然后还是向面试官求证确认不仅中所有单词要出现，并且出现的次数要大于等于子集中的。

一开始想着只能多重遍历去看看words1中单词是否每个都符合words2是其子集，然后想到了用一个二维数组来记录words2中每个单词中每个字母出现的次数。

和面试官讲了一下思路，他说思路是对的，让我写出来，边写边优化

想着能优化的点是讲长度为26个字母的数组变成Map，通过kev-value来记录字母出现的次数，但实际上时间复杂度还是一样的。

然后面试官提示可以看样例4，能不能将word2中的所有单词合并起来，如何合并？

这下子我就能想到了，计算words2中每个元素出现每个字母的次数，记录下字母出现最多的次数，组成一个新的子集，后面思路就差不多了。

回来之后靠着记忆在力扣找到这道题，直接一次过，看了下官方解法思路也一致。

function wordSubsets(words1: string[], words2: string[]): string[] {
    const map = new Map()
    for(const w of words2) {
        const m = new Map()
        for(const c of w) {
            // 记录下该子集每个字母出现的次数
            const count = (m.get(c) || 0) + 1
            m.set(c, count)
        }
        for(const [k, v] of m.entries()) {
            // 记录字母出现次数的最大值
            if (!map.has(k) || map.get(k) < v) {
                map.set(k, v)
            }
        }
    }
    const ans = []
    for(const w of words1) {
        const wm = new Map()
        // 统计word1每个字母出现的次数
        for(const c of w) {
            const count = (wm.get(c) || 0) + 1
            wm.set(c, count)
        }
        let flag = true
        // 检查 word1 是否包含 map 中所有的字符并且出现的次数等于或者更大
        for(const [k, v] of map.entries()) {
            if(!wm.has(k) || wm.get(k) < v) {
                flag = false
                break
            }
        }
        if(flag) {
            ans.push(w)
        }
    }
    return ans
};