原题
我们给出两个单词数组 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 <= 100001 <= A[i].length, B[i].length <= 10A[i]和B[i]只由小写字母组成。A[i]中所有的单词都是独一无二的，也就是说不存在i != j使得A[i] == A[j]。
解题思路1
这道题的一般思路很简单。循环A，然后循环B，B中的字符串中的字符如果在A的字符串中存在，则移除掉该字符，然后循环下一个字符。代码如下：
class Solution {
func wordSubsets(_ A: [String], _ B: [String]) -> [String] {
let array = A.filter { (s) -> Bool in
for b in B {
var s = s
for bCharacter in b {
if let index = s.firstIndex(of: bCharacter) {
s.remove(at: index)
} else {
return false
}
}
}
return true
}
return array
}
}
这个思路验证时，提示会超时。也就是性能不达标。
解题思路2
我们注意到示例3中，存在两个相同的字母”oo“。
示例 3：
**输入：**A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
输出：["facebook","google"]
我的优化思路是，把不重复的字符单独优化，重复的仍然按照“思路1”的方式进行处理。代码如下：
class Solution {
func wordSubsets(_ A: [String], _ B: [String]) -> [String] {
var bSet = Set<Character>()
var bArray = [String]()
B.forEach {
let set:Set<Character> = Set($0)
if set.count == $0.count { // no duplicated
bSet = bSet.union(set)
} else {
bArray.append($0)
}
}
let array = A.filter { (s) -> Bool in
// bSet filter
let aSet:Set<Character> = Set(s)
guard aSet.isSuperset(of: bSet) else {
return false
}
for b in bArray {
var s = s
for bCharacter in b {
if let index = s.firstIndex(of: bCharacter) {
s.remove(at: index)
} else {
return false
}
}
}
return true
}
return array
}
}
进行验证。还是性能不达标。
最终的解题思路
没办法，只好去翻评论。结果有人说，必须全部优化重复的字母，不然就一定会超时。所谓全部优化，就是把B中所有重复的字母计算出来。
原题的B等价于所有的字母都存在，且出现的次数大于等于B中的字符串中出现的那个字符的最多次数。
单独计算B的字母频率。
func characterFrequencies(in array:[String]) -> Dictionary<Character,Int> {
var dictionary = Dictionary<Character,Int>()
for s in array {
var sDic = [Character:Int]()
for c in s {
if let f = sDic[c] {
sDic[c] = f + 1
} else {
sDic[c] = 1
}
}
sDic.forEach { (c, f) in
if let frequency = dictionary[c] {
dictionary[c] = max(frequency, f)
} else {
dictionary[c] = f
}
}
}
return dictionary
}
完整代码：
class Solution {
func wordSubsets(_ A: [String], _ B: [String]) -> [String] {
let dictionary = characterFrequencies(in: B)
let array = A.filter { (s) -> Bool in
for (c,f) in dictionary {
var index = s.startIndex
for _ in 1...f {
if index < s.endIndex, let firstIndex = s[index...].firstIndex(of: c) {
let nextIndex = s.index(after: firstIndex)
index = nextIndex
} else {
return false
}
}
}
return true
}
return array
}
func characterFrequencies(in array:[String]) -> Dictionary<Character,Int> {
var dictionary = Dictionary<Character,Int>()
for s in array {
var sDic = [Character:Int]()
for c in s {
if let f = sDic[c] {
sDic[c] = f + 1
} else {
sDic[c] = 1
}
}
sDic.forEach { (c, f) in
if let frequency = dictionary[c] {
dictionary[c] = max(frequency, f)
} else {
dictionary[c] = f
}
}
}
return dictionary
}
}
小结
我们经常需要用到字典结构来挺高应用的性能。
