Maximum product of word lengths in Python

Question

Problems was to calculate maximum product of word lengths:

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".
Example 2:
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".
Example 3:
Given ["a", "aa", "aaa", "aaaa"]
Return 0

My answer is correct and passed all the test cases. I am looking to get some code review on this.

class Solution(object):
 def maxProduct(self, words):
 """
 maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters
 >> maxProduct(["eae", "ea", "aaf", "bda", "fcf", "dc", "ac", "ce", "cefde", "dabae"])
 >> 15
 """
 max_product = 0
 words = sorted(words, key=len, reverse=True)
 for index, j in enumerate(words):
 for i in words[index + 1:]:
 count = 0
 for k in i:
 if k in j:
 count = 1
 break
 if not count:
 m = len(j)
 n = len(i)
 word_product = m * n
 if ((m == n) or (m > n and n == m - 1)) and word_product > max_product:
 return word_product
 if word_product > max_product:
 max_product = word_product
 return max_product

Answer 1

My solution is quite different, let me explain it:

At first I define a small helper to check if two words have any letter in common, it may also be in-lined, but I like small functions.

def common(a, b):
 """
 >>> common("hello", "hi")
 {'h'}
 """
 return set(a) & set(b)

Then I define the relevant score function for the strings, as you see, after defining our criteria we are almost done.

def product_score(w1, w2):
 """
 >>> product_score("foo", "bar")
 9
 >>> product_score("foo", "fuu")
 0
 """
 return 0 if common(w1, w2) else len(w1) * len(w2)

The last step is very easy. We already know the criteria, so we can just map it over the combination of 2 of the input list and take the max:

def maxProduct(words):
 """
 Maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters.
 >>> maxProduct(["eae", "ea", "aaf", "bda", "fcf", "dc", "ac", "ce", "cefde", "dabae"])
 15
 """
 return max(product_score(w1, w2) 
 for (w1, w2) in itertools.combinations(words, 2))

I think my solution is more readable, mainly because it uses smaller functions and because it uses already existing wheels (standard library modules).

• Barry: I think you want 0 for the common letters case to handle the example.
• Gareth Rees: The OP processes the words in reverse order by length, which allows early exit when no further improvement is possible. I don't see this feature in your proposed solution.
• Caridorc: @GarethRees Yes, but he uses N log N time at first for sorting. So the early abort possibility has a cost. Only benchmarking can tell us which solution is more efficient.
• Gareth Rees: When you say "more efficient", do you mean "faster"?
• Caridorc: @GarethRees yes, I meant run-time efficiency

Answer 2

Avoid introducing so many variables

We have a ton of variables here: index, i, j, k, m, and n. They're all semi-important, and who knows what they mean. Try to avoid this proliferation. We can use itertools.combinations to pairwise iterate to avoid your top two loops:

for w1, w2 in itertools.combinations(words, 2):
 ...

We can introduce a new function to check that the words are disjoint:

def disjoint_words(a, b):
 return not (set(a) & set(b))
for w1, w2 in itertools.combinations(words, 2):
 if disjoint_words(w1, w2):
 ...

And then just use len when doing the lengths:

def maxProduct(words):
 max_product = 0
 words = sorted(words, key=len, reverse=True)
 for w1, w2 in itertools.combinations(words, 2):
 if disjoint_words(w1, w2):
 cur = len(w1) * len(w2)
 if (len(w1) in (len(w2), len(w2) + 1) and
 cur > max_product):
 return cur
 max_product = max(cur, max_product)
 return max_product

This is a lot more manageable.

• python: What happened to all the comments?
• Hammerite: In addition to there being a lot of variables, they could also be better names (why is j the outer loop variable and i the inner, which isn't idiomatic in any language community afaik? why does j correspond to m and i to n, which swaps the alphabetic order of characters? i and j are also more commonly used for integer loop variables, and I don't think most people would expect to see them used for strings)