一、题目描述

给你一个字符串数组 words ,找出并返回 length(words[i]) * length(words[j]) 的最大值,并且这两个单词不含有公共字母。如果不存在这样的两个单词,返回 0

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最大单词长度乘积( LeetCode 318 ):https://leetcode-cn.com/problems/maximum-product-of-word-lengths/
class Solution {
    public int maxProduct(String[] words) {

        // 获取字符串数组的长度
        int n = words.length;

        // 创建一个与 words 同等长度的 masks
        int[] masks = new int[n];

        // 每一个字母是否出现在某个单词的状态用一个 int 表示, int 的每一位代表 a - z 中的每个字母是否出现过
        // 比如 a 对应的是 000001
        // 比如 b 对应的是 000010
        // 比如 c 对应的是 000100
        // 这样的话,ab 对应的是 000011

        for (int i = 0 ; i < n ; i++) {

            String word = words[i];

            int bit = 0;

            // 对于 word 中的每个字母来说,都拿出来查看
            // 假设字符串为 "abc" 
            // 令字符串中的每一个字符命名为 c 
            // 则 (c - 'a') 为 0 1 2 
            // bit |= 1 << (c - 'a') 则是将 1 左移 0 位、1位、2位 
            // bit 开始位为 0 
            // 0 | 1 = 1 
            // 1 | 10 = 11
            // 11 | 100 = 111
            // 因此,字符串为 "abc"  对应的就是 111
            for (int j = 0; j < word.length(); j++) {

                int c = word.charAt(j) - 'a';

                // bit |= 1 << (c - 'a') 则是将 1 左移 (c - 'a')位
                bit |= (1 << c);

            }

            // 因此,字符串为 word 对应的就是 bit
            masks[i] = bit;
        }

        // 开始计算最大值
        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 在查看的过程中,如果发现两个单词不含有公共字母才计算它们的最大值
                if ((masks[i] & masks[j]) == 0) {
                    // 计算之后更新
                    ans = Math.max(ans, words[i].length() * words[j].length());
                }
            }
        }

        // 返回结果
        return ans;
    }

}

2、C++ 代码

3、Python 代码

四、动画理解(没有声音)

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。