leetcode刷题笔记318题 最大单词长度乘积

leetcode刷题笔记318题 最大单词长度乘积

源地址：318. 最大单词长度乘积

问题描述：

给定一个字符串数组 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
解释: 不存在这样的两个单词。

//核心问题： 判断两个单词之间的是否存在重复字母
//核心思想： 使用一个32位数的每位的01情况标注当前字母是否出现
//构建数组strArr存储每个单词的字母情况
//当i对应的字母情况与j对应的字母情况取与不为0 则存在重复字母
object Solution {
    def maxProduct(words: Array[String]): Int = {
        val strArr = Array.fill(words.length)(0)
        for (i <- 0 to words.length-1) {
            var temp = 0
            var word = words(i)
            for (char <- word){
                temp |= (1 << (char - 'a'))
            }
            strArr(i) = temp
        }

        var res = 0
        for (i <- 0 to words.length-1) {
            for (j <- i+1 to words.length-1) {
                if ((strArr(i) & strArr(j)) == 0){
                    res = math.max(res, words(i).length * words(j).length)
                }
            }
        }

        return res
    }
}

func maxProduct(words []string) int {
    arrStr := make([]int, len(words))
    for i, word := range words {
        temp := 0
        for _, strChar :=  range word {
            temp |= (1 << (strChar - 'a'))
        }
        arrStr[i] = temp
    }

    res := 0
    for i := 0; i < len(words); i++ {
        for j := i+1; j < len(words); j++{
            if arrStr[i] & arrStr[j] == 0{
                res = max(res, len(words[i]) * len(words[j]))
            }
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}