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

本文主要是介绍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<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 = 0n = len(words)bits = [0]*nfor 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;
}

这篇关于LeetCode - 318 最大单词长度乘积（Java JS Py C）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！