题目

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。

假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

示例 1:输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"] 输出: 16

解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。

示例 2:输入: words = ["a","ab","abc","d","cd","bcd","abcd"] 输出: 4

解释: 这两个单词为 "ab", "cd"。

示例 3:输入: words = ["a","aa","aaa","aaaa"] 输出: 0

解释: 不存在这样的两个单词。

提示：2 <= words.length <= 1000

1 <= words[i].length <= 1000

words[i] 仅包含小写字母

注意：本题与主站 318 题相同

解题思路分析

1、内置函数；时间复杂度O(n^3)，空间复杂度O(1)

func maxProduct(words []string) int {
   res := 0
   for i := 0; i < len(words); i++ {
      for j := i + 1; j < len(words); j++ {
         if strings.ContainsAny(words[i], words[j]) == false &&
            res < len(words[i])*len(words[j]) {
            res = len(words[i]) * len(words[j])
         }
      }
   }
   return res
}

2、位运算；时间复杂度O(n^2)，空间复杂度O(n)

func maxProduct(words []string) int {
   res := 0
   arr := make([]int, len(words))
   for i := 0; i < len(words); i++ {
      for _, char := range words[i] {
         // 位或 只要有1，那么就是1
         arr[i] = arr[i] | 1<

总结

Medium题目，题目同leetcode 318.最大单词长度乘积