Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/318.html
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.
Algorithm
Use mask
.
Because the title is all lowercase letters, so there are only 26 digits, and an integer int
has 32 digits.
We can use the last 26 digits to correspond to 26 letters. If it is 1, it means that the letter in the corresponding position has appeared.
Then each word can be represented by an int number.
The condition that two words have no common letter is that the two int numbers ‘&’ op are 0
Code
-
public class Maximum_Product_of_Word_Lengths { public class Solution { public int maxProduct(String[] words) { if (words == null || words.length <= 1) { return 0; } int n = words.length; int[] encodedWords = new int[n]; // setup encoding map for (int i = 0; i < words.length; i++) { String word = words[i]; for (int j = 0; j < word.length(); j++) { char c = word.charAt(j); encodedWords[i] |= (1 << (c - 'a')); // set to 1 for bit c-'a' } } int maxLen = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if ((encodedWords[i] & encodedWords[j]) == 0) { maxLen = Math.max(maxLen, words[i].length() * words[j].length()); } } } return maxLen; } } } ############ class Solution { public int maxProduct(String[] words) { int n = words.length; int[] masks = new int[n]; for (int i = 0; i < n; ++i) { for (char c : words[i].toCharArray()) { masks[i] |= (1 << (c - 'a')); } } int ans = 0; for (int i = 0; i < n - 1; ++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; } }
-
// OJ: https://leetcode.com/problems/maximum-product-of-word-lengths/ // Time: O(N^2) // Space: O(N) class Solution { public: int maxProduct(vector<string>& A) { int N = A.size(); if (N == 0) return 0; vector<int> bit(N); for (int i = 0; i < N; ++i) { for (char c : A[i]) { bit[i] |= (1 << (c - 'a')); } } int ans = 0; for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { if ((bit[i] & bit[j]) == 0) { ans = max(ans, (int)(A[i].size() * A[j].size())); } } } return ans; } };
-
class Solution: def maxProduct(self, words: List[str]) -> int: n = len(words) mask = [0] * n for i, word in enumerate(words): for ch in word: mask[i] |= 1 << (ord(ch) - ord('a')) ans = 0 for i in range(n - 1): for j in range(i + 1, n): if mask[i] & mask[j] == 0: ans = max(ans, len(words[i]) * len(words[j])) return ans ############ class Solution(object): def maxProduct(self, words): """ :type words: List[str] :rtype: int """ bitmap = [0] * len(words) mask = 0x01 ans = 0 for i in range(0, len(words)): word = words[i] for c in word: bitmap[i] |= (mask << (ord(c) - ord('a'))) for i in range(0, len(words)): for j in range(0, i): if bitmap[i] & bitmap[j] == 0: ans = max(ans, len(words[i]) * len(words[j])) return ans
-
func maxProduct(words []string) int { n := len(words) mask := make([]int, n) for i, word := range words { for _, c := range word { mask[i] |= (1 << (c - 'a')) } } ans := 0 for i := 0; i < n-1; i++ { for j := i + 1; j < n; j++ { if mask[i]&mask[j] == 0 { ans = max(ans, len(words[i])*len(words[j])) } } } return ans } func max(a, b int) int { if a > b { return a } return b }