LeetCode 318. 最大单词长度乘积

LeetCode 318. 最大单词长度乘积

题目描述

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
示例 1：
输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词为 "abcw", "xtfn"。

LeetCode 318. 最大单词长度乘积
提示：

    2 <= words.length <= 1000
    1 <= words[i].length <= 1000
    words[i] 仅包含小写字母

一、解题关键词

二、解题报告

1.思路分析

2.时间复杂度

3.代码示例

class Solution {
public int maxProduct(String[] words) {
        int len = words.length;
        int[] mask = new int[len];

        for(int i = 0;i < len;i++){
            String word = words[i];
            int wordLen = word.length();
            for(int j = 0;j < wordLen;j++){
                mask[i]  |= 1<< (word.charAt(j) - 'a');
            }
        }
        int maxProd = 0;
        for(int i = 0;i < len;i++){
            for(int j = i + 1;j < len;j++){
                if((mask[i] & mask[j]) == 0){
                    maxProd = Math.max(maxProd,words[i].length() * words[j].length());
                }
            }
        }
        return maxProd;

    }
}

2.知识点

位运算 动态规划

总结