LeetCode 961.单词子集

题目描述

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

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

如果对 B 中的每一个单词 bb 都是 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. 1 <= A.length, B.length <= 10000
  2. 1 <= A[i].length, B[i].length <= 10
  3. A[i] 和 B[i] 只由小写字母组成。
  4. A[i] 中所有的单词都是独一无二的,也就是说不存在 i != j 使得 A[i] == A[j]。

解题思路:

对于任意一个字母,它在B中单词中出现的最大次数,不能大于它在A中单词中的出现次数,否则这个A中的单词就不是符合要求的“通用单词”。

利用B中对于每一个字母出现次数取最大值的方法构建一个table,这个table是用来存放B中每一个字母出现次数最大值,对于A中每一个的单词都必须满足table中每一个不等于0的字母出现的次数需要大于等于table中的次数,此时则放入ret中

代码示例(C++):

class Solution {
public:
    vector<string> wordSubsets(vector<string>& A, vector<string>& B) {
        vector<vector<int> > mapa(A.size(), vector<int>(26, 0));
        vector<vector<int> > mapb(A.size(), vector<int>(26, 0));

        vector<int> table(26, 0);
        vector<string> ret;

        for (int i = 0; i < A.size(); ++i) {
            for (int j = 0; j < A[i].size(); ++j) {
                mapa[i][A[i][j] - 'a'] ++;
            }
        }

        for (int i = 0; i < B.size(); ++i) {
            for (int j = 0; j < B[i].size(); ++j) {
                mapb[i][B[i][j] - 'a'] ++;
            }
            for (int j = 0; j < 26; ++j) {
                if (mapb[i][j] > table[j])
                    table[j] = mapb[i][j];
            }
        }

        for (int i = 0; i < A.size(); ++i) {
            bool flag = true;
            for (int j = 0; j < 26; ++j) {
                if (table[j] != 0 && mapa[i][j] < table[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                ret.push_back(A[i]);
        }

        return ret;
    }
};
喜欢()
评论 (0)