318.Maximum Product of Word Lengths

Tags: [bit], [bit_map], [string]

Link: https://leetcode.com/problems/maximum-product-of-word-lengths/\#/description

Given a string arraywords, find the maximum value oflength(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.

Example 1:

Given["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return16
The two words can be"abcw", "xtfn".

Example 2:

Given["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return4
The two words can be"ab", "cd".

Example 3:

Given["a", "aa", "aaa", "aaaa"]
Return0
No such pair of words.

Solution: bit, bit_map

class Solution(object):
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        if not words or len(words) < 2:
            return 0

        num_of_words = len(words)
        values = [0 for _ in xrange(num_of_words)]
        for i in xrange(num_of_words):
            w = words[i]
            for c in w:
                values[i] |= (1 << (ord(c) - ord('a')))

        max_product = 0
        for i in xrange(len(words)):
            for j in xrange(i + 1, len(words)):
                if i == j:
                    continue

                if (values[i] & values[j] == 0) and max_product < len(words[i]) * len(words[j]):
                    max_product = len(words[i]) * len(words[j])

        return max_product

Revelation:

• Use "integer" to record what chars one word has, because there are only 26 types of chars (lower case) in English, which guarantee the 32 bits integer must can contains all type of chars for one word.
• If the the char in one word, we can mark '1' in binary presentation.
• integer_1 & integer_2 == 0 means there is no shared chars between two words.
• Here we use 'values' array to store all these integers.
• The inner loop starts from (i + 1), because for example we have checked the words[1] and words[2], we don't need check words[2] and words[1].

Note:

• Time complexity = O(n * k + n ^ 2), n is number of words, and k is the length of the longest word.

Time Limited Exceeded:

class Solution(object):
    def maxProduct(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        if not words or len(words) < 2:
            return 0

        max_product = 0
        for i in xrange(len(words)):
            for j in xrange(len(words)):
                if i == j:
                    continue

                if self.is_valid(words[i], words[j]):
                    max_product = max(max_product, len(words[i]) * len(words[j]))

        return max_product

    def is_valid(self, w1, w2):
        char_set = set(list(w1))
        for c in w2:
            if c in char_set:
                return False

        return True

Note:

• Time complexity = O(n^2 * k), n is the number of words, and k is the length of the longest word.