[Swift]LeetCode318.最大单词长度乘积|MaximumProductofWordLengths

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10260623.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16 
Explanation: The two words can be "abcw", "xtfn".

Example 2:

Input: ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4 
Explanation: The two words can be "ab", "cd".

Example 3:

Input: ["a","aa","aaa","aaaa"]
Output: 0 
Explanation: No such pair of words.

给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。

示例 1:

输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "xtfn"。

示例 2:

输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。

示例 3:

输入: ["a","aa","aaa","aaaa"]
输出: 0 
解释: 不存在这样的两个单词。

332 ms

 1 class Solution {    
 2     func maxProduct(_ words: [String]) -> Int {
 3         if words.isEmpty {
 4             return 0
 5         }
 6         
 7         let products = words.map{ProductHelper($0)}
 8         
 9         var res = 0
10         
11         for i in 0..<products.count {
12             for j in i+1..<products.count {
13                 let p1 = products[i]
14                 let p2 = products[j]
15                 if p1.characters & p2.characters == 0 {
16                     res = max(p1.count * p2.count, res)
17                 }
18             }
19         }
20         
21         return res
22     }
23 }
24 
25 class ProductHelper {
26     let count : Int
27     let characters : Int
28     init(_ s : String) {
29         count = s.count
30         let arr = s.unicodeScalars
31         var r = 0
32         for c in arr {
33             r |= 1 << Int(c.value - 97) 
34         }
35         characters = r
36     }
37 }

804ms

 1 class Solution {
 2     func maxProduct(_ words: [String]) -> Int {
 3         let aValue = "a".unicodeScalars.first!.value
 4         if words.count <= 1 { return 0 }
 5         var array = [Int]()
 6         for word in words {
 7             var a = 0
 8             for c in word.unicodeScalars {
 9                 a = a | (1 << (c.value - aValue))
10             }
11             array.append(a)
12         }
13         
14         var result = 0
15         for i in 0 ..< array.count - 1 {
16             for j in 1 ..< array.count {
17                 if array[i] & array[j] > 0 {
18                     continue
19                 }
20                 result = max(result, words[i].count * words[j].count)
21             }
22         }
23         return result
24     }    
25 }