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

• Java
• C++
• Python
• Go

• 
  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
  }
  

All Problems

All Solutions