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

IT行业相对于一般传统行业，发展更新速度更快，一旦停止了学习，很快就会被行业所淘汰。所以我们需要踏踏实实的不断学习，精进自己的技术，尤其是初学者。今天golang学习网给大家整理了《GoJava算法最大单词长度乘积示例详解》，聊聊算法、Java、单词长度、乘积，我们一起来看看吧！

最大单词长度乘积

给你一个字符串数组 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  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;
    }
}
</integer></integer></integer>

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  ans {
                        ans = tmp
                    }
                }
            }
            m[h] = len(word)
        }
    }
    return ans
}

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

n：数组长度

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

空间复杂度：o（n）

理论要掌握，实操不能落！以上关于《GoJava算法最大单词长度乘积示例详解》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！