Go Java算法最大单词长度乘积示例详解

2024-10-03 05:12:34

最大单词长度乘积

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

*示例 1：

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]

输出：16

解释：这两个单词为 "abcw", "xtfn"。

示例 2：

输入：words = ["a","ab","abc","d","cd","bcd","abcd"]

输出：4

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

示例 3：

输入：words = ["a","aa","aaa","aaaa"]

输出：0

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

方法一：位运算（java）

为了得到最大单词长度乘积，朴素的做法是，遍历字符串数组 words 中的每一对单词，判断这一对单词是否有公共字母，如果没有公共字母，则用这一对单词的长度乘积更新最大单词长度乘积。

题目约定了每个单词仅包含小写字母，所以，我们可以将单词中的每个字母都映射到一个 int 类型的不同位上，这样，就做到了每个单词都对应一个 int 类型的数值，这样的话，我们对比两个单词是否包含相同的字母，只需要把它们对应的 int 数值做 & 运算，看是不是等于 0 即可，如果等于 0 ，说明没有相同的位是 1，也就不存在相同的字母。

这样，我们在比较两个单词是否没有公共字母的时候只要直接按位与一下即可，没有公共字母应该得到的值是0，其他情况得到的值都不为零。

class Solution {
    public int maxProduct(String[] words) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int length = words.length;
        for (int i = 0; i < length; i++) {
            int mask = 0;
            String word = words[i];
            int wordLength = word.length();
            for (int j = 0; j < wordLength; j++) {
                mask |= 1 << (word.charAt(j) - 'a');
            }
            if (wordLength > map.getOrDefault(mask, 0)) {
                map.put(mask, wordLength);
            }
        }
        int maxProd = 0;
        Set<Integer> maskSet = map.keySet();
        for (int mask1 : maskSet) {
            int wordLength1 = map.get(mask1);
            for (int mask2 : maskSet) {
                if ((mask1 & mask2) == 0) {
                    int wordLength2 = map.get(mask2);
                    maxProd = Math.max(maxProd, wordLength1 * wordLength2);
                }
            }
        }
        return maxProd;
    }
}

l：数组中所有单词的长度之和

n：数组长度

时间复杂度：o（l+n^2）

空间复杂度：o（n）

方法一：位运算（go）

具体的方法思路已经在上文中表述，详情请看上文内容

func maxProduct(words []string) int {
    hash := func(word string) int {
        res := 0
        for _, r := range word{
            res |= 1 << (r - 'a')
        }
        return res
    }
    m, ans := map[int]int{}, 0
    for _, word := range words {
        h := hash(word)
        if m[h] < len(word) {
            for other, v := range m {
                if((other & h) == 0){
                    if tmp := v * len(word); tmp > ans {
                        ans = tmp
                    }
                }
            }
            m[h] = len(word)
        }
    }
    return ans
}