8
\$\begingroup\$

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
\$\endgroup\$
10
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I think you want 0 for the common letters case to handle the example. \$\endgroup\$ – Barry Dec 30 '15 at 0:15
  • \$\begingroup\$ 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. \$\endgroup\$ – Gareth Rees Dec 30 '15 at 11:55
  • \$\begingroup\$ @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. \$\endgroup\$ – Caridorc Dec 30 '15 at 12:41
  • \$\begingroup\$ When you say "more efficient", do you mean "faster"? \$\endgroup\$ – Gareth Rees Dec 30 '15 at 14:05
  • \$\begingroup\$ @GarethRees yes, I meant run-time efficiency \$\endgroup\$ – Caridorc Dec 30 '15 at 14:05
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What happened to all the comments? \$\endgroup\$ – python Dec 30 '15 at 0:13
  • \$\begingroup\$ 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) \$\endgroup\$ – Hammerite Dec 31 '15 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.