leetcode 916 单词子集

忘是亡心i 2023-07-02 07:26 12阅读 0赞

我们给出两个单词数组 A 和 B。每个单词都是一串小写字母。

现在，如果 b 中的每个字母都出现在 a 中，包括重复出现的字母，那么称单词 b 是单词 a 的子集。 例如，“wrr” 是 “warrior” 的子集，但不是 “world” 的子集。

如果对 B 中的每一个单词 b，b 都是 a 的子集，那么我们称 A 中的单词 a 是通用的。

你可以按任意顺序以列表形式返回 A 中所有的通用单词。

示例 1：

输入：A = \["amazon","apple","facebook","google","leetcode"\], B = \["e","o"\]  
输出：\["facebook","google","leetcode"\]  
示例 2：

输入：A = \["amazon","apple","facebook","google","leetcode"\], B = \["l","e"\]  
输出：\["apple","google","leetcode"\]  
示例 3：

输入：A = \["amazon","apple","facebook","google","leetcode"\], B = \["e","oo"\]  
输出：\["facebook","google"\]  
示例 4：

输入：A = \["amazon","apple","facebook","google","leetcode"\], B = \["lo","eo"\]  
输出：\["google","leetcode"\]  
示例 5：

输入：A = \["amazon","apple","facebook","google","leetcode"\], B = \["ec","oc","ceo"\]  
输出：\["facebook","leetcode"\]

提示：

1 <= A.length, B.length <= 10000  
1 <= A\[i\].length, B\[i\].length <= 10  
A\[i\] 和 B\[i\] 只由小写字母组成。  
A\[i\] 中所有的单词都是独一无二的，也就是说不存在 i != j 使得 A\[i\] == A\[j\]。

思路： 题目长的题，一定要弄清题目要求。可以单个出现重复。即b的单个重复出现不打紧。桶排序的思路。

但是这里要稍微处理一下B数组即可每次选最大的。这是因为b的每个单词可以重复出现，但是单个单词字符出现的次数不能超过A的单词字符数。

class Solution {
        public List<String> wordSubsets(String[] A, String[] B) {
            List<String> res = new ArrayList<>();
            int[] cnt = new int[26];
            for (int i = 0;i < B.length;i++) {
                String str = B[i];
                int[] dp= new int[26];
                for (char c:str.toCharArray()) {
                    dp[c-'a']++;
                }
                for (int o = 0;o < 26;o++) {
                    cnt[o] = Math.max(cnt[o],dp[o]); 
                }  
            }
            for (int i = 0;i < A.length;i++) {
                String cur = A[i];
                int[] d = new int[26];
                for (int m = 0;m < cur.length();m++) {
                    d[cur.charAt(m) - 'a']++;
                }
                int j = 0;
                for (;j < 26;j++) {
                    if (cnt[j] > d[j] ) {
                        break;
                    }
                }
                if (j == 26) 
                    res.add(cur);
    
            }
            return res;
        }
    }