LeetCode 318.最大单词长度乘积(中等)

abcabc lv.1

发布时间：2023-09-08 00:06:18 127

题目描述:

给定一个字符串数组 words ，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。

示例 1:

输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16 
解释: 这两个单词为 "abcw", "xtfn"。

示例 2:

输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4 
解释: 这两个单词为 "ab", "cd"。

示例 3:

输入: ["a","aa","aaa","aaaa"]
输出: 0 
解释: 不存在这样的两个单词。

提示:

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

题目分析:

这道题首先要做的就是判断两个字符串中是否含有重复的字母，解决了这个问题也就解决了这道题的关键点。你可能想到用暴力求解，但这道题运用位运算的方法就能解决这个关键问题。我们可以为每个字符串建立一个长度为 26 的二进制数字，每个位置表示是否存在该字母。如果两个字母串含有重复数字，那它们的二进制表示的按位与不为 0。我们可以先用循环遍历这个数组，然后获取对应单词的位掩码。最后再进行一次循环，通过计算它们的位掩码按位与是否结果为 0 判断是否包含重复字母，如果没有重复的字母，则计算它们的长度之积，并与最大单词长度乘积进行比较，保留其中最大的值。最后返回最大单词长度乘积值即可。当然下面的解法是使用数组的形式，但你也可以使用 map 对其进行优化。

题解:

执行用时: 7 ms

内存消耗: 38.3 MB

class Solution {
    public int maxProduct(String[] words) {
        // 单词个数
        int n = words.length;
        // 单词位掩码数组
        int[] masks = new int[n];
        // 单词长度数组
        int[] lens = new int[n];

        // 临时位掩码
        int bitmask = 0;
        // 循环遍历每个单词
        for (int i = 0; i < n; ++i) {
            bitmask = 0;
            // 获取单词对应的位掩码
            for (char ch : words[i].toCharArray()) {
                // (int)ch - (int)'a' 是计算该字母在掩码中的位置
                // 1 << x 创建一个第 x 位为 1 的掩码
                // bitmask |= x 通过或操作将该码合并到位掩码中
                bitmask |= 1 << ((int)ch - (int)'a');
            }
            // 保存单词的位掩码
            masks[i] = bitmask;
            // 保存单词的长度
            lens[i] = words[i].length();
        }

        // 最大单词长度乘积
        int maxVal = 0;
        // 循环
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                // 判断两个单词是否包含公共字母
                if ((masks[i] & masks[j]) == 0) {
                    // 如果没有则计算它们长度的乘积并与原来的最大乘积比较
                    maxVal = Math.max(maxVal, lens[i] * lens[j]);
                }
            }
        }

        // 返回最大长度乘积
        return maxVal;
    }
}

题目来源:力扣(LeetCode)

文章来源： https://blog.51cto.com/u_15891283/5886586

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。