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).

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.