Hex.*

LC318 - Maaximum Product of Word Lengths

Posted on In
Datastructure and Algorithm: DAY 90. Leetcode: 286/2752

Description

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:

1
2
3
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

Example 2:

1
2
3
Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".

Example 3:

1
2
3
Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.

Constraints:

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

Solution

  1. create a list called s to store all the individual letter of each word
  2. using two for loops to compare each two words in the list, if there is no common letter, update the answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# O(n^2) time | O(n) space
class Solution:
    def maxProduct(self, words: List[str]) -> int:
        ans = 0
        d = []
        for word in words:
            d.append(set(list(word)))

        for i in range(len(words)):
            for j in range(i+1, len(words)):
                if not d[i] & d[j]:
                    ans = max(ans, len(words[i])*len(words[j]))
        return ans