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

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

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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 合并成一个单词  
思路参考[本题官方题解][Link 1]。

## 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;
        }
    }

[Link 1]: https://leetcode.cn/problems/word-subsets/solution/dan-ci-zi-ji-by-leetcode/