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.

这个题主要是怎么辨别两个字符串有相同的字母,使用一个32位的int,使用其中的26位来记录一个词中出现了哪些字母,那么只要把这个int相与就知道两个字符串是不是有重复字母了,没有重复字母的话这个结果应该是0,接下来计算乘积就好了。

var maxProduct = function(words) {
    var words_array = [];
    words.forEach(function(word){
        var len = word.length;
        var tmp_num = 0;
        for(var i=0;i<len;i++){
            tmp_num |= (1<<(word.charCodeAt(i)-48));
        }
        words_array.push(tmp_num);
    });
    var words_len = words_array.length;
    var ret = 0;
    var tmp = 0;
    words_array.forEach(function(word,s){
        for(var j=s+1;j<words_len;j++){
            if((words_array[j] & words_array[s])===0){
                tmp = words[j].length*words[s].length;
                if(tmp>ret){
                    ret = tmp;
                }
            }
        }
    });
    return ret;
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容