LeetCode318: Maximum product of word lengths

难度：medium
本题同时也是《剑指offer 专项突击》的第5题【Integer Topic】.

problem

https://leetcode.cn/problems/aseY1I/
or
https://leetcode-cn.com/problems/maximum-product-of-word-lengths/

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

初步解法

The key to this problem is to determine whether two strings have the same characters.The most intuitive is scanningstr1Whether each character in is present in str2中.这里不再赘述.

Use a hash table to record the occurrence of characters in a string

Simply put, build one26*n的表,n表示words中单词个数.The value of each coordinate is 0 或1 ,代表第ndoes not appear in any of the words ‘a’,‘b’,‘c’….The specific method is to create a dictionary,key为26个字母字符, value为列表,eg.,[0,1,1,0,1,0] 这种.
代码：

class Solution:
    def maxProduct(self, words) -> int:
        t1 = time.time()
        dictw = dict()
        for k in range(ord('a'),ord('z')+1):
            dictw[chr(k)] = []
            for wl in range(len(words)):
                if chr(k) in words[wl]:
                    dictw[chr(k)].append(1)
                else:
                    dictw[chr(k)].append(0)
        num_max = 0
        for ii in range(len(words)-1):
            for jj in range(ii+1, len(words)):
                flag = 0
                for k in dictw.keys():
                    if dictw[k][ii] and dictw[k][jj]:
                        flag+=1
                if flag==0:
                    num_max = max(num_max, len(words[ii])*len(words[jj]))

测试用例：

words =["gfgc","bfdcabbbdbfd","acbeaacfecfbdagaebbeagddgb","fdfefbgffegfcc","cagcbgg","eff","fcdabfcaa","gggdcfacfcdeecfdcbfaeadbec","eaccfagbcagafagfebgdc","aaebefcebcfe","ebdcge","aaeecgcacaece","gfgdafecedbgbaccggegbadfcca","bebefebffdfabcfdg","fdcdaggdcaceabgadgbgab","agdcggbcdagbbcbgaeagaggf","caccecbaggfa","ecegegdcaef","ffaadgaedggabaccebggc","acgaeeafffbbebfcdfdgebcbbg","aacdefgfbaedggfe","bbcfgddgeafcfdbadccgade","bddeacgaggfeeageaaagaccdga","ge","gbgbgebefgefddfdfg","adfdeegacaeabafeafeggdbdabe","ggafeacfgeafggfefggb","afggdcacfafbdcgbb","agedabcfb","dgdbfa","cccgcdfedafgbccdbagebe","dgaadebcggbagbafgbaaecd","gg","fggbeeefdcgcfaeacbbadbfgd","abdegggfeacfcacgceadgbfddc","febd","afdabadgeedbcg","ggc","acefcbec","eaeffebcfgeffccafdb","aeedfc","eabcd","cfafcecbdegd","bgegdccdcgebbecegbgg","bdadfdgdceegd","gefecgbacedcafcgeec","bdfbbac","debgcggbggbaeacgaddcbbefcde","fccfe","acfacgaegeg","cdcfecadbfcag","efc","caccdaafegbdaafedbabfebfe","dcbedbaagbccd","gcbgceaefgfbceegf","ab","aee","aaa","gecaccebbbdgd","eeaafgcggedbgcfadcedffgb","abcbbgddfbecceebg","fd","bccgcgagcdd","ccagbdfagdecgdc","fcbfedaagde","cgcebebecfgffgcdgc","cbeedgdgecbfcfdcgbdbcd","cagccdedbffcfabcacegbe","bgfbebdbbecabgagafagcecdabf","bcddffgefeaabbddedgbee","abbfade","agggbebegcegebfe","baaecbgbdaaaged","fad","daccccdfdgedbdgebcaeeecaba","cfeffaegg","bcaac","aadbcbddedbbabf","bdcfegccfgefb","aab","fggagcf","be","eabf","cbg","cbggbededceffddabbfcg","aegdfffdbc","ffggdgga","aeb","gfbdeegadccdbgedcebce","ebcgdbc","aad","fegeeeeaccfbfdgdefgef","fbgaaaddcf","ceebfdegcegdgdcbbddadfe","egdbfabgfafgaeafagb","cbdg","ebceedadcfd","cbbgecfeegbadbea","cgccbfbgaaeceff","ebcffgbfdggfbbgdeeaddbdec","dbcbddgdcegbabbgfgecdbgfe","cddfgcfbabdffaadfgeebdgd","cfcaaafaab","cegdaafcffbfedgaeeedbecb","fdaeggagcaecadadaacgfdg","fafagffbegcedededaaeaf","bbdabacabcfgage","edeaddebgagacdagecebebge","eeecfg","eefbcefdcabadecgfcfdfgefa","dgccagdaed","bbegfdfeacaddgacddbbfgcfde","bdc","affgecdbgeebffdfadg","adcafc","cbagc","cbbffebea","agfa","efbcffegabfeggdegdd","eededbdegdefeebfebbaf","agacdagfebdadaddedcddg","bafadccdfdbcfbbdgagafg","ebaefgfg","ecgbacffdfgdagae","gfedefgecbcffagbagbeeefaeab","dabebafabcfebbebbda","agdgedccdccdgcbgdcebfbaccf","fagacdccbgagabebac","efaeb","bbfadbbgdcgbefdfbeededabd","gc","ddebgedfgcfeedgdbagebfceafe","gadeabb","cecgeagddcdf","gbccdgccccgbdcbebabebfba","deegcee","fcedcabeg","gdfdgebggcadaeafcddbeegfc","agcfdbdg","bbafdbdccdcfgfe","fcbcdee","ebeddcagadccbadd","afadebbefcddgdg","acfdeedcgdcecfagacdacg","bcdbcgegegdgcdcgcfcggafda","acdcfaacedegebccc","addabdcgegdcdbbaeabfggg","fcedefdeeaeaeab","befdggaff","eafggc","dcdccadcdfebca","eedecdbcgfeabggbge","edccadbgeggb","bbagdcfbaac","fegfddaeedfd","abdgeaefbefdfdgb","eadegdd","cdcffaadfcaedeeegacc","bafaebcgaca","feeggdbgfeecgfefabccg","fegaddf","bfgffgffdffcffagbdc","bgcbcdbdgcfga","ddegbbfa","ddedccefecdgfdaccdadfffbaeb","cfgbfaaabbbbgaeabadccdeeff","fddgdbeabfggafdgcbede","gggfffgdgdgdfdcaefegd","fdc","fffcgfeadadgefcgaefccff","gggebebfgggfeeafbbdefb","afedacbeffefcfddbfdaefdfd","bbdffgacfgaebcab","bcfeggaecbeafcddgbbgce","dfgffbeegbba","gadbf","egcbgedgda","fbfbefce","cfdcacfcdgbaagag","egaae","edbabfcfcddgfffbggecfdbfcfg","ef","bfagffb","adgcdbaafagd","dfgeeddggaebabececbbeba","aabccfgggafgbebac","acgc","dcfbdbgfg","fcbgacfbde","fabdadadgfc","dggfegee","dgggaefeddaeafggaa","geegfabeeadddgbgegagdcecbad","ffbeacbegecegdaadcc","facbfdeeafddececf","fddfebfd","efb","egebdfggdccdecdcdagfgacdcc","eeebbdbefcdfacdbc","aaedbedfaegadfagec","agcddbab","ffabffgdgcdbeeacgagfae","ggfea","begdg","ceddafddgb","bafgbddabefbgedagadgeadg","gbcfbgf","gagfggdbfccc","cffag","cccegcfagdeefggbdcf","adcdgac","ffbg","ccgcedecceb","adegacd","egbbgfacg","cabece","bcaeaecddbefbdf","edbedbag","eaffdgfgcdbdfdccagaad","fdfgebddgbebgbbbdffge","eadaccgbaf","aedfeccdffeffabgdfbea","bdceebcgaccedbdabffdffbfag","fdgfegeeabeegbcaebdf","cdebccda","ddabfdfbefbeaecbcabcdbd","fdedeeadcbedfdbdfgcf","cfgabaefcbdfcbfdbbcafdcdeb","fecccacgcecgcbbadabbcace","caadeeadbfgebdbaa","bcbgbffcbbbfbf","bfgdfeac","fceccaagaa","bagbcfefbeddgec","cdfbbbbadeacacbgaffccfbegg","adcageadebeecgdeefegfaaadde","daabfggdeafebeaad","addaefbefbdfgegdbcffgdedefe","ddadbbcccfbacaceffde","bggeagfedg","bfgabcbbcdbgdgg","cefeagbcfae","ceafefb","gcbdegfaeaegbc","dcgcefdcgfggeefbeacebfg","ccdfce","faccebdgcbegeedccfeececbc","efabeaacfddacadfgfcgd","addfaeaaafffd","agc","edfdgcabecffacefdcecfbfegc","ddaeaeaeccedgbccfefbee","ag","cedfcacaagadfcgddcgb","dfagcceccgdbbcdc","gbceee","edfdaabeedbfea","cgbcaeaebafcbccbcdbecgcdbg","ffadceefbfeccebf","gf","edacdffff","egbf","fefgfeecfgfdag","afeaaebcbcacgcgdde","cgffbafeggggdbeebabg","bbgggfadbecegdaafcg","db","bddgaaaacbfgagfd","becfaabeedcgg","bagggagfdcggdgfbfc","fbafcefbefbcaeceabdegdef","gfccggfgefd","cfdebac","dfbcfecdgfgfbggdggaabcee","acddabagddggaeefdbbcfebbfd","gabcceafdcaeefbae","fegcecgeggbdgcbcdg","baffcegadcfaffbfcbedaecaf","dbdaedcgcgbcgcacafabgca","dgbeccbbbcdegffe","eeadefede","cedbgfgeabcgagebe","ffdceegagcffdgdbcfbffdgcg","gcdbddgcd","ccddagaafaabebaabg","dedfgdefecfgggbbcececdg","fdbfadd","dgbdgdg","aefgbcbed","daaaebcfefddfcfffadbgab","egeefeaeddbgfaag","cbaaaagceeddefeecbbcgeagcdf","gggddccfaca","cefgedgdcdgaadabcabfac","faceedgecbcd","ecebb","gagfddfggcefgdgggfe","gc","bcbdacdeacdbcd","gddcabaececbdbbeaadfagf","abddceebgfga","edgcgcfggafbbcgfcadfaaddc","cggbcccfbab","fbcgggf","aacceefbdcfdfebeb","dabaebfbfgcddc","faedc","gfgaede","decfccbgbgdcbffeafg","abaf","dgdfdagagbd","gddcacg","gbfff","fcddcfdeaddebdbeffeeaacbbe","feffeccbgcadfffge","gfgbagfae","gfceaeabbgebaedafacbg","gfcbgccgd","deggbcc","gdcb","adcdffbebccbfdbacaagdaacdg","bbadcbgffgaaeecfagbfcf","adffcgeedfcafcebagdfdaagd","cfefc","efcc","eadgdbfggbfafabaa","gffdbcbcbbece","cgfccdbfffef","abcgbcbfcebeg","dega","fcecfeadaf","eefcfafecabgeedgae","bcagdcfgggcg","adcgbabcebcfaeacgg","babgbdbgbgb","eabdbacacdddd","fcgabbbgadgeceefdgedbdbbg","efc","bbbgacfbdffbgbe","feccbdecaggad","ebadefcfcbgbcbafgbfebf","bcadaeeaeceefgcgbcb","gcbceg","ffcaecgfebgeefegdeceefgge","abagd","fbdbedd","gac","babafgdfdggfgcdfdeb","fgbgcgcafacfbd","gc","ffecccgcgfbgdgedbefgcb","cfd","egfgfagecbaacaadfdf","faebcffaee","gbfcb","bacbgddcfbegbdacaggag","egfgcacgggecdgbegaeg","feafadgfcgegbeccbfcfefabb","dcbga","bbeeegfgedfd","bacdcg","aebgdcgdebcf","dbbaefcdfcadacebddfbcgg","egfbggabgadcdffafdaeebgdc","eadgbeccbgdffffcgfedfbbdbf","fbaabcadgebgebbacfg","eafdefaaacfbgggafbfb","febf","fbdfedcgaagaegdedgebedecg","aeecaegf","aeeff","daeccfeaabfabe","afcbdgge","agebffcbbcccaccf","bfddagefagbbaaeeadc","feagagebgg","aacgcagbcfceacdbfdedefgga","egaffdbg","edfdcfbeecgbbbdegdcegff","cac","agcbfbcafaeccfcdfdgg","ebedbbcga","fdbgge","caceagefebcggfffdfabegg","afbbagdeeaccgeedebdaeca","faeeddgfddddfddebgcfebaf","dbfedfdcdgcdbcb","dfcg","cg","ddagebcacadafa","baagcccfdfcecaabdcbbea","daefbfdgbeadbfgbade","bdfbddecfeebccbdfbfe","egcbddfddebfgefaacbcc","eab","dedcbgcd","bgggdeegdedfcecbbfgc","bbcggfeggcbfgaecgacbc","bcefeedaadgccg","ggffddegcdcgbfgadfgfbdagcg","dedbfbbgefgbacgbg","cbeeffefaeadgfebgecgaea","gfafgbf","bbaccgfagd","ddacbdegcdcdf","eafabfdccdec","adaaddbfaddcgeddgab","dcdcddbdgfcefbefedabe","egbbagadcecacdbgbccecfg","abfb","eegdbdga","ddcbffegdffga","cfab","bc","bac","aaeadfcgaeaecfdbfdadaf","gbgaa","cfcgceeabefcefdadbac","ffddddfgaddbcdfg","fgedabedegaaddea","gfefdfgfeddedc","cddbgbgbacfgb","edeedgeddadeecgd","eagbgggadgbgbfdcaccb","gadggdedfbgfgbfbffaadcccb","bddecffdffbbecdebgfdegc","baeaff","fcgba","bd","acabe","dceegeefbgbga","dgbff","ceegcabefecabggdbdbbg","cfecdffeggecdbb","dbff","fea","aegdbcbbbebdabbde","gf","eddafcfbaabfcgfaebcdfa","acdfcbdg","febagcdbfcedd","eebdfadbeaedadddgbaebeegfd","bbfcfbbedbbd","agecfeggedgafa","edbcgdcdebbfccaca","ffegcaggegeggcdegbgbgfb","bfbfacdgffgbbedcafdcdcfga","gbbfbeffegbaaf","gggbgfeddgcbfceeb","effgbbacbafgagedfe","gbdaeaaeg","fe","cddegcgbfggbfb","bfc","bcafcfgcfbeedafafecdgfc","eefeefcbedegaggb","dabafddcdfbdfgdcdabbdcafbga","bbdgbcdedgbecfbcacaafca","fcbedfbgcaffceeffbebcfbbf","bdecgfccedabd","cgfcdbgecbg","egdfada","fcgeceegac","bebged","cbefbcafdccffgdefcd","cd","cdcgafefdfgggfadccffdfg","aa","bcffaccaf","fdbfgcdfcg","dfaafffbdfgdbcebcfbeddgd","aaggcfbaddfcfa","abgfgagaebadec","adegcbd","gbbdebebfd","cdbbcecefagfffecdagded","fedcbcfbbdadceacc","gdfdccaadga","ffbeafgecbcfaddcefgee","efgdgdbcgcffb","bccgcgb","fgfdcacbafedg","eeegccbd","cgad","adffdegdaefcbcegafdbd","cebgadbfgg","babbcfecd","adaabfefaacfe","gbcbgebdefcedefdccadga","dbbfdccccbcbefffebcegefefca","geacdeefaagac","ccddgggdfbcgbcaedbf","fccdbgfdege","deebaedabcgdfefdacae","abaebbcaefcgdedabf","daccdaagdfg","fggdf","adagfbceabdafgegccd","ffdagbefbddafffdbeeecgd","gefgag"]

时间：0.2157015800476074

优化

来自：老汤 简单易懂Java/C++ /Python/js/go - 最大单词长度乘积
简单来说,is to create such a dictionary：{表示abcdsituation occurs26位二进制整数 : 单词长度}, such as words ‘abcd’ 就是 { [1111 00000000…] : 4},为了表示方便,You can convert the previous list to decimal integers as keys.At the same time for the same key value,Directly take the maximum word length update.
Turn the more complicated bit operations of the original blog into a list.

完整代码

import time
import math
class Solution:
    def maxProduct(self, words) -> int:
        t1= time.time()
        bitmask_map, ans = {
    }, 0
        for k in range(len(words)):
            length = len(words[k])
            bitmask =[]
            for abc in range(ord('a'), ord('z')+1):
                abc = chr(abc)
                # 循环'a' 到'z',看看 abc 是否存在于第 k 个词中, 以26stored in binary code
                if abc in words[k]:
                    bitmask.append(1)
                else:
                    bitmask.append(0)
            # 26位二进制码 转为 十进制整数, as dictionary keys
            bitmask = int(''.join(list(map(str,bitmask))), 2)
            # Here is the merge abc The same words appear
            if bitmask in bitmask_map:
                bitmask_map[bitmask] = max(length, bitmask_map[bitmask] )
            else:
                bitmask_map[bitmask] = length
        
        # Pairwise match in the dictionary 算 Maximum length product
        for x in bitmask_map:
            for y in bitmask_map:
                if x&y ==0:
                    ans = max(ans, bitmask_map[x] * bitmask_map[y])
        print(time.time()-t1)
        return ans