Study Plan For Algorithms - Part44

1. 单词长度的最大乘积
给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。
方法一：

def maxProduct(words):map_dict = {}n = len(words)res = 0ascii_A = ord('a')for i in range(n):temp = 0for c in words[i]:temp |= 1 << (ord(c) - ascii_A)if temp in map_dict:map_dict[temp] = max(len(words[i]), map_dict[temp])else:map_dict[temp] = len(words[i])for keyA in map_dict.keys():for keyB in map_dict.keys():if (keyA & keyB) == 0:res = max(res, map_dict[keyA] * map_dict[keyB])return res

方法二：

def maxProduct(words):n = len(words)word_sets = [set(word) for word in words]max_product = 0for i in range(n):for j in range(i + 1, n):if all(char not in word_sets[j] for char in word_sets[i]):product = len(words[i]) * len(words[j])max_product = max(max_product, product)return max_product

方法三：

def maxProduct(words):n = len(words)lengths = [len(word) for word in words]bit_representations = []for word in words:bit_rep = 0for char in word:bit_rep |= 1 << (ord(char) - ord('a'))bit_representations.append(bit_rep)max_product = 0for i in range(n):for j in range(i + 1, n):if bit_representations[i] & bit_representations[j] == 0:max_product = max(max_product, lengths[i] * lengths[j])return max_product