题目连接
单词长度的最大乘积
思路
我没有想出来
这是我看别人的思路的
此题的关键字在于如何表示两个不含有公共字母的字符串
即只关注不同，对于相同的我不在乎。对于这种问题，可以用二进制来解决，这里谈到了二进制，一般来说就是用位运算，那么如何将一个字字符串用位运算来表示
| 字母 | 次序 | 维权 |
|---|---|---|
| a | 0 | 2 0 2^{0} 20 |
| b | 1 | 2 1 2^1 21 |
依次类推
那么对于abc,就可以转换为
1 + 2 + 4 = 7，这个过程可以看成1 | 2 | 4
那么判定两个字符串是否有相同的部分就直接将经过处理的两个字符串按位与，看结果是否为0，若为0则两个字符串不会有相同的部分
好搞定，代码就很简单了
class Solution {public int maxProduct(String[] words){// 由于此题的关键在于如何将两个字符串之间的不同之处表示出来// 联想到二进制，既然要用到二进制那么就要将数组的每一个元素转换为数字// 不如这样 a 是 0 占据 2^0// b 是 1 占据 2^1// c 是 2 占据 2^2// d 是 3 占据 2^3////int res = 0;int[] bits = new int[words.length];for(int i = 0;i <bits.length;i++){char[] cs = words[i].toCharArray();for(int j=0;j<cs.length;j++){bits[i]|=(1<<(cs[j]-'a'));}}for(int i=0;i<words.length;i++){for(int j=i+1;j<words.length;j++){if((bits[i] & bits[j]) == 0){res = Math.max(res,words[i].length() * words[j].length());}}}return res;}
}就比如说abc 转换之后的结果是 1 + 2 + 4=7
b的转换结果是2，将 7 | 2 =1不等于0则它们有相同的部分
其实如果题目是返回两个字符串相同的部分可以根据bits[i]和bit[j]的结果反推回去，若结果是6,那么转换为二进制是110,4+2，对应字符串bc,也可以是cd，看你怎么处理的
总结
- 对于关注相同或不相同的问题，可以联想到位运算，若要用到位运算，则需要将对象的每一个元素所在的位置转换成二进制位权
