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

08-23 37阅读 0评论

最大单词长度乘积

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

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

n:数组长度

时间复杂度:o(l+n^2)

空间复杂度:o(n)

以上就是GO java算法最大单词长度乘积示例详解的详细内容,更多关于go Java算法单词长度乘积的资料请关注云初冀北其它相关文章!

免责声明
本站提供的资源,都来自网络,版权争议与本站无关,所有内容及软件的文章仅限用于学习和研究目的。不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负,我们不保证内容的长久可用性,通过使用本站内容随之而来的风险与本站无关,您必须在下载后的24个小时之内,从您的电脑/手机中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。侵删请致信E-mail:goliszhou@gmail.com
$

发表评论

表情:
评论列表 (暂无评论,37人围观)

还没有评论,来说两句吧...