leetCode-318:Maximum Product of Word Lengths

问题描述

给定一个字符串（由小写字母组成）列表，要求找出两个不包含相同字母的字符串的最大长度乘积。题目链接：**点我**

样例输入输出

输入：[“abcw”,”baz”,”foo”,”bar”,”xtfn”,”abcdef”]

输出：16

解释：两个字符串为 abcw 和 xtfn，长度分别是 4 和 4，结果是 4 * 4 = 16

输入：[“a”,”ab”,”abc”,”d”,”cd”,”bcd”,”abcd”]

输出：4

问题解法

此题主要难点在判断两个字符串是否包含相同的字母，最简单的做法是对字符串的每个字母进行比较，但这样会超时，稍微优化点的做法是用 set 来存储字母，将某个字符串加到另外的字符串 set 里，根据 set 的长度变化来判断是否有相同字符，但是这样也会超时，再优化的做法是把字符串字符按位或运算得到一个数字，然后依次对每个字符串或运算的数字进行与运算，如果结果为 0， 说明两个字符串不包含相同的字母，否则说明两个字符串包含相同的字母。对上述满足要求的字符串的长度进行两两相乘，可以找到最大的结果。代码如下

class Solution {
    public int maxProduct(String[] words) {
        int[] chs = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            int num = 0;
            for (char ch : words[i].toCharArray()) {
                num |= 1 << (ch - 'a');
            }
            chs[i] = num;
        }
        
        int result = 0;
        for (int i = 0; i < chs.length; i++) {
            for (int j = 0; j < chs.length; j++) {
                if ((chs[i] & chs[j]) == 0) {
                    result = Math.max(result, words[i].length() * words[j].length());
                }
            }
        }
        return result;
    }
}

参考资料

https://leetcode.cn/problems/maximum-product-of-word-lengths/solution/gong-shui-san-xie-jian-dan-wei-yun-suan-cqtxq/