肇鑫的技术博客

业精于勤,荒于嬉

"916. 单词子集"的解题思路

916. 单词子集

原题

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

现在,如果 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]

解题思路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
    }
}

小结

我们经常需要用到字典结构来挺高应用的性能。