Leetcode 318. Maximum Product of Word Lengths

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析： Version 1每次迭代都需要进行两次set转换，Version 2预先进行了set转换，效率有提升。由于Version 2中两个字符串的与运算非常耗时，因此Version 3先将字符串转换为代表字符串的数字，然后进行与运算，这样两个字符串的与运算就变成了两个数字按位进行与运算，大大减少了运行时间。Version 4将代表数字一样的字符串进行了合并，并保留了最大的字符串长度，这样减少了与运算的迭代次数，并且不影响最终结果。

• Version 1

class Solution:def maxProduct(self, words: List[str]) -> int:words.sort(key=len, reverse=True)maximum = 0n = len(words)for i in range(n):for j in range(i+1, n):x = len(words[i])y = len(words[j])if maximum >= x * y:return maximumintersection = set(words[i]) & set(words[j])if len(intersection) == 0:maximum = max(maximum, x * y)breakreturn maximum

• Version 2

class Solution:def maxProduct(self, words: List[str]) -> int:chars = [set(word) for word in words]maximum = 0n = len(words)for i in range(n):for j in range(i+1, n):x = len(words[i])y = len(words[j])intersection = chars[i] & chars[j]if len(intersection) == 0:maximum = max(maximum, x * y)return maximum

• Version 3

class Solution:def maxProduct(self, words: List[str]) -> int:lengths = [len(word) for word in words]flags = []for word in words:flag = 0for ch in word:flag = flag | (1 << (ord(ch) - 97))flags.append(flag)maximum = 0n = len(words)for i in range(n):for j in range(i+1, n):if flags[i] & flags[j] == 0:maximum = max(maximum, lengths[i] * lengths[j])return maximum

• Version 4

class Solution:def maxProduct(self, words: List[str]) -> int:maximum = 0mapping = {
    }for word in words:flag = 0for ch in word:flag = flag | (1 << (ord(ch) - 97))mapping[flag] = max(mapping.get(flag, 0), len(word))for key1, value1 in mapping.items():for key2, value2 in mapping.items():if key1 & key2 == 0:maximum = max(maximum, value1 * value2)return maximum

Reference

1. https://leetcode.com/problems/maximum-product-of-word-lengths/