0916. Word Subsets

题目信息

题号:

0916

难度:

Medium

主题:

字符串、字符多重集合、通用单词

原题:

LeetCode 0916

重点:

对 words2 中每个单词都要满足包含关系;字符按出现次数比较而非只比较是否出现,结果可按任意顺序返回

题目重述

给定两个小写字符串数组 words1 和 words2。若单词 b 中每个字符的出现次数都不超过单词 a 中对应字符的出现次数,则称 b 是 a 的子集。

若 words2 中的每个单词都是某个 words1 单词 a 的子集,则 a 是通用单词。请返回 words1 中所有通用单词;返回顺序不限。

两个数组长度均在 [1, 10^4] 范围内,每个单词长度在 [1, 10] 范围内,且只包含小写英文字母;words1 和 words2 各自包含的字符串互不重复。

自建示例

同时满足两个字符需求:

输入:words1 = ["abbc","aabbcc","abc","abbbc"], words2 = ["ab","bc"]
输出:["abbc","aabbcc","abc"]
解释:通用单词至少要包含一个 a、一个 b 和一个 c。前三个单词满足要求;"abbbc" 不含 c。输出顺序可以不同。

重复字符必须达到要求次数:

输入:words1 = ["aab","ab","aaab"], words2 = ["aa"]
输出:["aab","aaab"]
解释:words2 要求至少两个 a;"ab" 只有一个 a,因此不是通用单词。