[LeetCode]318. 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.

Example 1:
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:
Given ["a", "aa", "aaa", "aaaa"]
Return 0
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;
}