LeetCode--318. Maximum Product of Word Lengths

本文主要是介绍LeetCode--318. Maximum Product of Word Lengths，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题链接：https://leetcode.com/problems/maximum-product-of-word-lengths/

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

问题要求找到长度乘积最大的一对单词，并且这两个单词没有相同的字母。刚拿到这个问题时，开始想到的就是暴力方法，枚举单词对，检查是否有相同字符，如果没有就进行乘积的比较。但在Discuss里发现了基于位运算的十分漂亮的解法，利用了32位int的二进制表达也具有编码特性，int的二进制表达从右往左bit位（26个bit位对应26个小写字母）上的1代表某个字母存在于该单词中，然后问题就归结为一个&位运算，十分精巧，代码如下：

class Solution {public int maxProduct(String[] words) {int[] mapBit=new int[words.length];for(int i=0;i<words.length;i++){for(int j=0;j<words[i].length();j++){mapBit[i] =mapBit[i] | (1<< (words[i].charAt(j)-'a'));}}int ret=0;for(int i=0;i<words.length-1;i++){for(int j=i;j<words.length;j++){if((mapBit[i] & mapBit[j])==0)ret=Math.max(ret,words[i].length()*words[j].length());}}return ret;}
}

 

这篇关于LeetCode--318. Maximum Product of Word Lengths的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---