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.
Example 1:
Given["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return16
The two words can be"abcw", "xtfn".
Example 2:
Given["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return4
The two words can be"ab", "cd".
Example 3:
Given["a", "aa", "aaa", "aaaa"]
Return0
No such pair of words.
题目
给定一组单词，计算没有重复字母的2个单词长度的最大乘积
方法
最麻烦的应该是判断2个单词有没有重复字母。假设单词第i位字母为c，该单词的值为val |= 1<<(c-'a')，遍历该单词每个字母后，就可以算出该单词的val了。c-'a'最大为26，因此1<<(c-'a')不会超过int范围。若val的第n位为1，那么该单词一定包含'a'+n对应的字母
c代码
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int maxProduct(char** words, int wordsSize) {
int i = 0;
int j = 0;
char *word = NULL;
int* vals = (int *)malloc(sizeof(int) * wordsSize);
for(i = 0; i < wordsSize; i++) {
word = words[i];
int wordLen = strlen(word);
int val = 0;
for(j = 0; j < wordLen; j++)
val |= 1 << (word[j]-'a');
vals[i] = val;
}
int product = 0;
int maxProduct = 0;
for(i = 0; i < wordsSize; i++) {
for(j = 0; j < wordsSize; j++) {
if((i != j) && ((vals[i]&vals[j])==0)) {
product = strlen(words[i]) * strlen(words[j]);
maxProduct = maxProduct>product?maxProduct:product;
}
}
}
return maxProduct;
}
int main() {
char* words[6] = {"abcw", "baz", "foo", "bar", "xtfn", "abcdef"};
assert(maxProduct(words, 6) == 16);
return 0;
}
