当前位置：首页 > news >正文

LeetCode //C - 318. Maximum Product of Word Lengths

news 2025/11/26 19:30:27

318. Maximum Product of Word Lengths

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

Example 1:

Input: words = [“abcw”,“baz”,“foo”,“bar”,“xtfn”,“abcdef”]
Output: 16
Explanation: The two words can be “abcw”, “xtfn”.

Example 2:

Input: words = [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
Output: 4
Explanation: The two words can be “ab”, “cd”.

Example 3:

Input: words = [“a”,“aa”,“aaa”,“aaaa”]
Output: 0
Explanation: No such pair of words.

Constraints:

2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] consists only of lowercase English letters.

From: LeetCode
Link: 318. Maximum Product of Word Lengths

Solution:

Ideas:

1. hasCommonLetters Function:

This function uses bit manipulation to determine if two words share any common letters. Each word is represented by a 26-bit integer, where each bit corresponds to a letter (‘a’ to ‘z’).
By iterating through each character of the words and setting the corresponding bit, we can check if any bit is set in both words using the bitwise AND operator.

2. maxProduct Function:

The main function iterates through all pairs of words, checking if they share any common letters using the hasCommonLetters function.
If they don’t share any letters, it calculates the product of their lengths and updates the maxProduct if the current product is greater.

3. Efficiency:

The solution is optimized using bit manipulation to quickly check for common letters, making it suitable for larger input sizes within the given constraints.

Code:

// Function to check if two words share common letters
int hasCommonLetters(const char* word1, const char* word2) {int letters1 = 0, letters2 = 0;// Mark presence of each character in the first wordwhile (*word1) {letters1 |= 1 << (*word1 - 'a');word1++;}// Mark presence of each character in the second wordwhile (*word2) {letters2 |= 1 << (*word2 - 'a');word2++;}// If there is any common letter, the AND of the two will be non-zeroreturn letters1 & letters2;
}int maxProduct(char** words, int wordsSize) {int maxProduct = 0;// Iterate through all pairs of wordsfor (int i = 0; i < wordsSize; i++) {for (int j = i + 1; j < wordsSize; j++) {// Check if words[i] and words[j] share common lettersif (!hasCommonLetters(words[i], words[j])) {int product = strlen(words[i]) * strlen(words[j]);if (product > maxProduct) {maxProduct = product;}}}}return maxProduct;
}