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

目录

题目来源

题目描述

示例

提示

题目解析

算法源码

---

题目来源

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

具体实现如下：

// 单词对应的二进制数
bit = 0 
 
// 遍历单词word的每一个字母letter
for (letter in word) {
    // 计算字母的偏移量
    offset = ascii(letter) - ascii('a')
    // 按位或
    bit |= 1 << offset    
}

上面按位或的运算，是为了将各个字母的偏移量都归纳到一个二进制数中。

按位或的特点是：操作数中只要有一个为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
            for(int j=0; j
                bits[i] |= 1 << (words[i].charAt(j) - 'a');
            }
        }
 
        for(int i=0; i
            for(int j=i+1; 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
        for(int j=0; j<strlen(words[i]); j++) {
            bits[i] |= 1 << (words[i][j] - 'a');
        }
    }
 
    for(int i=0; i
        for(int j=i+1; j
            if((bits[i] & bits[j]) == 0) {
                ans = MAX(ans, strlen(words[i]) * strlen(words[j]));
            }
        }
    }
 
    return ans;
}