LeetCode_哈希表_中等_916.单词子集-蒲公英云

LeetCode_哈希表_中等_916.单词子集

Bertha 。 2023-10-07 19:54 142阅读 0赞

1.题目

给你两个字符串数组 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 <= 104
1 <= words1[i].length, words2[i].length <= 10
words1[i] 和 words2[i] 仅由小写英文字母组成
words1 中的所有字符串互不相同

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/word-subsets

2.思路

（1）暴力穷举法
暴力穷举法比较容易想到，即使用 2 层 for 循环来进行判断（在此之前还可以先对 words2 中的单词进行去重处理），但是该方法的时间复杂度较高，在 LeetCode 中提交时会出现“超出时间限制”的提示！

（2）将 words2 合并成一个单词
思路参考本题官方题解。

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        Set<String> hashSet = new HashSet<>(Arrays.asList(words2));
        List<String> res = new ArrayList<>();
        int len2 = hashSet.size();
        for (String a : words1) {
            int cnt = 0;
            for (String b : hashSet) {
                if (isSubset(a, b)) {
                    cnt++;
                } else {
                    break;
                }
            }
            if (cnt == len2) {
                res.add(a);
            }
        }
        return res;
    }
    //判断 b 是否为 a 的子集，如果是则返回 true，否则返回 false
    public boolean isSubset(String a, String b) {
        char[] ach = a.toCharArray();
        char[] bch = b.toCharArray();
        Map<Character, Integer> hashMap = new HashMap<>();
        for (char c : ach) {
            hashMap.put(c, hashMap.getOrDefault(c, 0) + 1);
        }
        for (char c : bch) {
            if (hashMap.containsKey(c) && hashMap.get(c) >= 1) {
                hashMap.put(c, hashMap.get(c) - 1);
            } else {
                return false;
            }
        }
        return true;
    }
}
//思路2————将 words2 合并成一个单词
class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        // words2Max 保存 words2 中字符串的每个字符出现的最大次数
        int[] words2Max = count("");
        for (String b : words2) {
            int[] bCount = count(b);
            for (int i = 0; i < 26; i++) {
                words2Max[i] = Math.max(words2Max[i], bCount[i]);
            }
        }
        List<String> res = new ArrayList<>();
        for (String a : words1) {
            boolean flag = true;
            int[] aCount = count(a);
            for (int i = 0; i < 26; i++) {
                if (aCount[i] < words2Max[i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                res.add(a);
            }
        }
        return res;
    }
    public int[] count(String s) {
        int[] res = new int[26];
        for (char c : s.toCharArray()) {
            res[c - 'a']++;
        }
        return res;
    }
}