LeetCode318：单词长度的最大乘积

乘积"/>

LeetCode318：单词长度的最大乘积

文章目录

• • problem
  • 初步解法
  • • 用哈希表记录字符串中出现的字符
  • 优化
  • 完整代码

problem

/
or
/

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

初步解法

这个问题的关键在于判断两个字符串有没有相同的字符。最直观的是扫描str1中的每个字符是否存在于str2中。这里不再赘述。

用哈希表记录字符串中出现的字符

简单来说就是建立一个26*n的表，n表示words中单词个数。每个坐标的值为0 或1 ，代表第n个单词中有没有出现 ‘a’,‘b’,‘c’…。具体做法就是建立一个字典，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 = 0for ii in range(len(words)-1):for jj in range(ii+1, len(words)):flag = 0for k in dictw.keys():if dictw[k][ii] and dictw[k][jj]:flag+=1if 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 - 最大单词长度乘积
简单来说，就是建立这样一个字典：{表示abcd出现情况的26位二进制整数 : 单词长度}， 比如对单词 ‘abcd’ 就是 { [1111 00000000…] : 4}，为了表示方便，可以把前面的这个列表转为十进制整数作为键值。同时对相同键值的，直接取最大单词长度更新。
把原博客比较复杂的位操作搞成了列表。

完整代码

import time
import math
class Solution:def maxProduct(self, words) -> int:t1= time.time()bitmask_map, ans = {}, 0for 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 个词中, 以26位二进制码形式存储if abc in words[k]:bitmask.append(1)else:bitmask.append(0)# 26位二进制码 转为 十进制整数, 作为字典键值bitmask = int(''.join(list(map(str,bitmask))), 2)# 这里是合并一下 abc 出现一样的词if bitmask in bitmask_map:bitmask_map[bitmask] = max(length, bitmask_map[bitmask] )else:bitmask_map[bitmask] = length# 字典里的两两匹配 算 长度乘积最大值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