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.
題目
給定一組單詞侥加，計算沒有重復(fù)字母的2個單詞長度的最大乘積
方法
最麻煩的應(yīng)該是判斷2個單詞有沒有重復(fù)字母矾湃。假設(shè)單詞第i位字母為c惹盼，該單詞的值為val |= 1<<(c-'a')丈咐，遍歷該單詞每個字母后灼伤，就可以算出該單詞的val了搏色。c-'a'最大為26仰猖，因此1<<(c-'a')不會超過int范圍芬探。若val的第n位為1神得，那么該單詞一定包含'a'+n對應(yīng)的字母
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;
}
