Maximum Product of Word Lengths

Problem

Given a string array words, find the maximum value of length(words[i]) * length(words[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:

Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".


Example 2:

Input: ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".


Example 3:

Input: ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.


Solution

集合暴力法

代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  class Solution: def maxProduct(self, words): """ :type words: List[str] :rtype: int """ max = 0 set_words = [set(list(w)) for w in words] for i,word_1 in enumerate(words): for j,word_2 in list(enumerate(words))[i+1:]: if not (set_words[i] & set_words[j]): l = len(word_1)*len(word_2) max = l if l>max else max return max 

评价

1. 使用集合虽然方便但集合运算耗时还是有的（对比与下面的位位运算
2. 在找最大值时没有好好利用Python自带的库函数和语法糖（自己写的就是比它慢！）

代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14  class Solution: def maxProduct(self, words): """ :type words: List[str] :rtype: int """ masks = {} start = ord('a') for w in words: mask = 0 for c in set(w): mask|=(1<

Single Number