LeetCode - 318 最大单词长度乘积（Java & JS & Py & C）

迷南。 2024-02-22 06:56 13阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

#### 题目来源 ####

[318. 最大单词长度乘积 - 力扣（LeetCode）][318. _ - _LeetCode]

#### 题目描述 ####

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

#### 示例 ####

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

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

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

#### 提示 ####

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

#### 题目解析 ####

本题首先需要遍历出两个单词words\[i\]和words\[j\]，之后如果将这两个单词逐字符比较的话，则肯定会超时。

一种优化策略是，将单词按照一定规则转化为二进制数，规则如下：

每个单词中的字母，都可以转化为相较于字母'a'的ASCII码偏移量，比如：

*  字母'b' 相较于 'a' 的偏移量是1
 *  字母'c' 相较于 'a' 的偏移量是2

如果我们将这些偏移量想象为二进制数的位，那么一个单词就可以转化为一个二进制数，比如：

> 单词"abc"，其中 'a' 的偏移量是0，'b'的偏移量是1， 'c'的偏移量是2
> 
> 则可得二进制数 0000 0111
> 
> ![daa2d510db4e4829ad41344320ab7644.png][]
> 
> 具体实现如下：
> 
>     // 单词对应的二进制数
>     bit = 0 
>     
>     // 遍历单词word的每一个字母letter
>     for (letter in word) {
>         // 计算字母的偏移量
>         offset = ascii(letter) - ascii('a')
>         // 按位或
>         bit |= 1 << offset    
>     }
> 
> 上面按位或的运算，是为了将各个字母的偏移量都归纳到一个二进制数中。
> 
> ![723abd2b86b746dfaa2cd175eb433a7f.png][]
> 
> 按位或的特点是：操作数中只要有一个为1，则结果为1，
> 
> 因此一个单词中出现重复字母也没事，因此1 | 1 = 1，利用此特点还可起到去重作用。

经过上面逻辑，我们就将单词转化为二进制数。

接下来单词之间比较是否存在相同字母，就可以转化为比较两个二进制数是否存在都为1的位。

而按位与&运算的特点是：

*  两个操作数都为1，结果才为1，即 1 & 1 = 1，
 *  有一个操作数为0，则结果为0，即 1 & 0 = 0，0 & 1 = 0

因此只要将两个单词对应二进制数进行按位与&运算，结果只要为0，则说明两个二进制数不存在同时为1的位，即两个单词不存在相同字母。

#### Java算法源码 ####

class Solution {
        public int maxProduct(String[] words) {
            int ans = 0;
    
            int n = words.length;
    
            int[] bits = new int[n];
            for(int i=0; i<n; i++) {
                for(int j=0; j<words[i].length(); j++) {
                    bits[i] |= 1 << (words[i].charAt(j) - 'a');
                }
            }
    
            for(int i=0; i<n; i++) {
                for(int j=i+1; j<n; j++) {
                    if((bits[i] & bits[j]) == 0) {
                        ans = Math.max(ans, words[i].length() * words[j].length());
                    }
                }
            }
    
            return ans;
        }
    }

#### JS算法源码 ####

/**
     * @param {string[]} words
     * @return {number}
     */
    var maxProduct = function (words) {
      let ans = 0;
    
      const n = words.length;
    
      const bits = new Array(n).fill(0);
      for (let i = 0; i < n; i++) {
        for (let j = 0; j < words[i].length; j++) {
          bits[i] |= 1 << (words[i][j].charCodeAt() - 97);
        }
      }
    
      for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
          if ((bits[i] & bits[j]) == 0) {
            ans = Math.max(ans, words[i].length * words[j].length);
          }
        }
      }
    
      return ans;
    };

#### Python算法源码 ####

class Solution(object):
        def maxProduct(self, words):
            """
            :type words: List[str]
            :rtype: int
            """
            ans = 0
    
            n = len(words)
    
            bits = [0]*n
            for i in range(n):
                for j in range(len(words[i])):
                    bits[i] |= 1 << (ord(words[i][j]) - 97)
            
            for i in range(n):
                for j in range(i+1, n):
                    if (bits[i] & bits[j]) == 0:
                        ans = max(ans, len(words[i]) * len(words[j]))
            
            return ans

#### C算法源码 ####

#define MAX(a,b) (a) > (b) ? (a) : (b)
    
    int maxProduct(char ** words, int wordsSize){
        int ans = 0;
    
        int* bits = (int*) calloc(wordsSize, sizeof(int));
    
        for(int i=0; i<wordsSize; i++) {
            for(int j=0; j<strlen(words[i]); j++) {
                bits[i] |= 1 << (words[i][j] - 'a');
            }
        }
    
        for(int i=0; i<wordsSize; i++) {
            for(int j=i+1; j<wordsSize; j++) {
                if((bits[i] & bits[j]) == 0) {
                    ans = MAX(ans, strlen(words[i]) * strlen(words[j]));
                }
            }
        }
    
        return ans;
    }

[318. _ - _LeetCode]: https://leetcode.cn/problems/maximum-product-of-word-lengths/description/
[daa2d510db4e4829ad41344320ab7644.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/26fcab2f9e3b47fd9a6aba473d362c10.png
[723abd2b86b746dfaa2cd175eb433a7f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/f4960c227048447c856e01b96c16539e.png