南阳网站建设电话,网站排名seo,烟台网站建设 烟台网亿网络公司,宁夏百度公司问题#xff1a;给定一个字符串数组words#xff0c;找到这样的最大值#xff1a;length(word[i]) * length(word[j])#xff0c;words[i]和words[j]没有共同的字母。假设输入字符串只包含小写字母。如果不存在这样的两个字符串#xff0c;则返回0。
思路#xff1a;难点…问题给定一个字符串数组words找到这样的最大值length(word[i]) * length(word[j])words[i]和words[j]没有共同的字母。假设输入字符串只包含小写字母。如果不存在这样的两个字符串则返回0。
思路难点是判断两个字符串是否包含相同字母。可以一个个遍历找到效率会比较低。看看用位运算能怎么做。一共26个小写字母。表示不同的字母可以用one-hot类型表示从词向量表示方法得到的启示。
z 10000…000(一共25个0) y 01000…000(一共25个0) … a 0000…001
用26位的二进制表示不同的字母。 这样一个字符串 abc 000….111 azc 100…..101 两个字符串的值做与操作。如果结果为0则说明没有相同字符。
public int maxProduct(String[] words) {int n words.length;int[] values new int[n];for (int i 0; i n; i) {for (int j 0; j words[i].length(); j) {//这样的表示是我之前没想到的values[i] | (1 (words[i].charAt(j) - a));}}int maxproduct 0;for (int i 0; i n - 1; i) {for (int j i 1; j n; j) {if ((values[i] values[j]) 0) {if (words[i].length() * words[j].length() maxproduct) {maxproduct words[i].length() * words[j].length();}}}}return maxproduct;}
参考资料 1 问题
