我目前正在leetcode.com上做一些编码问题,并且由于输出相同结果的两个算法之间的计算时间差异而难以接受.
问题:给定一个字符串数组字,找到length(word [i])*length(word [j])的最大值,其中两个字不共享公共字母.您可以假设每个单词仅包含小写字母.如果不存在这两个单词,则返回0.
在最低限度,人们需要比较字符串对的每个组合,以便计算答案.我觉得bitwise更快/更有效率,但我选择忽略它为了这个问题.
您可以在本文的底部找到我正在使用的测试用例单词列表.
算法1:
curr_max=0
for i in range(0,len(words)):
for j in range(0,len(words)):
if i<j:
curr_word=set(words[i])
other_word=words[j]
for char in curr_word:
if char in other_word:
break
else:
curr_max=max(curr_max,len(words[i])*len(other_word))
print(curr_max)
这个算法本质上是一个嵌套的for循环,它比较了每个可能的单词组合,如果不是"if i",它将包括双重计数和自身计数.
算法2:
curr_max = 0
while words:
curr_word = set(words[0])
curr_len = len(words[0])
words = words[1:]
for word in words:
for char in curr_word:
if char in word:
break
else:
curr_max = max(curr_max, curr_len*len(word))
print(curr_max)
该算法基本上将列表中的第一个单词与所有其他单词进行比较,然后将其从列表中删除并重复该过程.它大约需要0.02秒,大约快4倍.我很难理解为什么差异如此之大.在此先感谢您的帮助!
我用来比较时间的输入是这样的:
words=["eedfdddadbcc","acdadecebafaebaec","dfde","ececbefe","bbafebbeccbddddbd","eafeffddbbbf","cbd","abadeaddfbcfbadb","ffdcacaebbeaa","fbadcfeede","bdcefdbfec","bbadfccdfebefd","dbefdfabededb","cbbccdecfbbe","abaeeecdbecebafedbfee","fbefbdfc","fffafb","bfadbdefbfedbddff","cbccbfdadbfe","bacaafecbbfaae","fcbffdbefcfbccd","fefaadfaaafdfbdaff","ecabaff","ccbdefcdcfac","bbbfafbffcefbc","edecefa","bcdfbcebabae","aaefecfcbbccfaeeaf","beaabaaeaebef","adfac","acedfdabccebc","efbfbef","bfccadbcbcfcdabfa","ffcaddbcf","dfae","ccadeeebeaabddebcadec","babaa","ebbdbaabddfdddad","fafaddbaebdaa","eeeeddadedfe","effbca","abcddfa","cbadcfeffeaaeecbbfe","ceaabcfaaaefeeadf","acecadddde","ece","dc","bfafdefbbdafacdcfb","fbdcad","dbaaffcdbcbdea","baaee","bebed","beaedceceaa","eacbcfdbcefbaddffcac","acddaedacfeedffad","efebff","efcbf","cdfffffaacfacafb","adacaceea","fceeffededbcfbfaaf","eafaeffcbfde","debadcddbdbabefdbe","ef","eeeeabfbaabddaecb","eeadcdcdaacaabe","ebcbffdefafdcbcebec","eb","adedefbaabfcefbea","ddceabfddaaefcea","ddffb","fdadfac","de","cbcdcbddcdabeb","ccffeeafbbbf","ccba","dab","bbdbeefdbef","cbec","ffcbefdbfdacdbdbf","adfad","ceacdcbfbdbbaebbd","ecfeaefff","ddbbdaefddeebd","eeeee","abdadc","eafecdbdef","aeedaeeaebaaeecdd","dddeebcbdea","bcaadedacb","ebdeadddcafa","ecbdbcbfccbdffaef","fddcffbfffa","accbdcfcedeabeab","cfbbefbddcaeecfbfacc","efffdaacbafeecdad","aaadfa","efeccbabdefaf","defebaddaafdcd","ecebcaacdaccaddcfeee","fdbbfecaffeafaa","bafccdbea","caa","deedefdeccead","bbfbfeaeddacfacea","daaefbbcbcdbfbfdda","aceed","cfeadadadbcff","eaefcdca","cefebdbaafeabdbdeaafd","abec","aeececad","cfeabcbaeaebdbcaada","aac","ebabffeb","fa","cf","dcebedefc","dbaedceecf","ffebaedafccceb","faefbeacaddefbe","eeadbfabfbbbfaeffaeea","affdecaca","ccfdcbdefcdfaddbbeaed","bc","feafaaabaceade","bebdfbbad","eeacaefaddacac","fff","aeddcd","ccffbabbdfc","ecddbcdeecdfbbb","debdbcdcafdcd","cfaebaeddbbd","efdada","becdccaeffeedcadbdd","feedbacc","cbbeebcdad","bfdcbdfdbcceadded","cfdbfdddafadadddcba","bcedeaeeaac","ffdcfccffdfffaebf","afffceaaadbbedfdd","faaeebdfbfefddebed","eedafbddeeaaadcdeaccc","eeceadafa","ebcfaccabea","eebdbbedcaedcbdcfaba","ecfcadaebacbdfdccebe","cbbabdadaee","cfeea","dec","cfedcbaabbaef","aacdabcbf","dfdbacadbebeedcd","bccccfdcdfe","cfcacdbcdccddcadce","dafafeccfaccaadeabbf","eaffaaffefccde","bbfbddccfda","fbdbbbbfbe","eafbcafbdbead","edbcdcefdc","fe","aafdcabce","ddafedceddcdcbfbcafe","dabcafbcfafeeadbbbef","beeaacd","cadeabebdbcfbbdfe","ecfefbfbbfa","fedacafcc","bcdcefecbcebaeeccdbd","fefde","cafba","bdabeaabbdbbbccecebda","dfeaadbeaaeefdfbed","dbaecde","cfbdfffbdeeeeb","fc","decadcacfaabca","cebbdff","badabbddcfed","fcce","fedfadefcf","acfccfbfcda","debfc","bebafeaeffe","ceaefbbcefacbbacb","cebbaeb","cadedfdafecdfb","bfefdfbaceddfcbade","cefeefaeddafbbdcade","faceadcefbffadb","cfbacafae","dfbfadfdccedbcbeaae","dbbccdddaf","ebbcbcebdddcedcfdcfaa","ccedffbcdbaedfaeb","ccfeaceaaaaeee","faade","afaaacaecbffdbadcbcd","cebfbbefbbdabbbffea","cdaadba","bbefdcacaaadbbbdedec","adabfbebdb","fcfefadcbadaacbdcfdbb","adddadebfc","fb","ecfebaacbdabece","dabacfdecfe","eeeecc","eabbe","fcdffababd","aafdbbcfdecbccca","efebaaadfecccecaa","cffefdbf","bcbdd","eaaccdcfdbbbcf"]
更新OP以帮助人们帮助我解决这个问题! 我现在用这个生成单词:
words = [''.join([choice('abcdefghijklmnopqrstuvwxyz') for _ in range(randrange(2, …