我在字谜中对单词进行分组时超时了，还有其他方法吗
I get a time exceeded for grouping words in anagrams , is there any other way
class Solution:
# @param {string[]} strs
# @return {string[][]}
def isAnagram(self, s, t):
s1 = [];s2 = []
s1[:0] = s
s2[:0] = t
s1.sort();s2.sort()
if s1 == s2:
return True
else:
return False
def groupAnagrams(self, strs):
l=[]
for i in strs:
m=[]
if m not in m:
m.append(i)
for j in strs:
if self.isAnagram(i,j)==True:
m.append(j)
strs.remove(j)
l.append(m)
return l
上面的代码当输入：
["shuffled","lacquered","efficacious","michigander","corruptness","internals","converter","speeds","rebellion","transceivers","electroencephalogram","crematories","bespoken","complainant","flotations","nev","blindfolding","corresponds","optionally","aggravating","gratifying","healthfulness","characterizing","dole","fantasies","bulks","responsibly","exploiting","confluences","header","dunno","saddam","adulate","spoken","bargained","funiculars","enlargements","mastered","expended","zambians","muggiest","riveted","junketing","shrewish","issachar","wallpapered","bridges","efficacious","cogitation","parabola","inheres","song","chock","surfing","windy","richer","shields","rehash","autobiographical","idiotic","discipline","keyword","proliferation","hollower","exposing","britain","fred","salarying","misplaying","gallbladder","czechoslovakia","burying","deprivation","lubricated","androids","hurtle","kitty","attach","subsidies","tumbled","unseemliest","impelling","surmise","blundered","etching","stuccoes","windiest","monorail","raided","comedians","theodora","muhammadans","sillies","unlocking","lubricating","desperados","vine","purposeless","calmest","loopy","confluences","clings","today","mountaineer","son","axiomatic","thur","ideograph","document","rudolf","joviality","crystals","moodiest","footprints","net","taney","crane","psycho","quantified","aisle","aimee","vegetarianism","canes","twining","butler","transporters","cohere","wilts","outlines","imbecile","passages","godunov","sunken","maneuvers","papyruses","slowed","residuals","tarpaulins","devour","callus","aldebaran","wraiths","outplay","psychoanalyst","flicking","congealing","unsteadier","smoother","bavarian","savvy","wino","tortola","stiflings","deprecation","iguassu","surnames","chit","fraud","strong","camel","undulate","jiggling","lars","singsonging","canny","someway","overtaken","sonja","rapacity","scotch","discus","spill","boated","americanized","phoneyed","nonprofessional","excessive","nuisance","haddock","fared","jibes","lintels","nurturing","falls","testimonial","pluralism","cookeries","cocksure","cassock","appraiser","contingent","barbarous","shoo","groundings","tulsa","hughes","fiver","taces","compatriot","cockpit","sepoy","naughties","topeka","decadents","rangers","topaz","kr","accoladed","palmed","jackknifes","overbore","blintze","shari","corroborations","mortgagees","tylenol","rockies","caesar","estimations","disconnects","coordinating","satinwood","octopus","smithsonian","dustiness","subscript","compacting","sanctuary","restarting","palmist","johnie","winos","conurbations","contrived","crumby","demavend","blooding","electrodes","composed","wheres","clements","ululate","basketball","cattlemen","callus","toolboxes","harelips","garaged","fuller","stubborn","scald","devotion","revolvers","kernels","lean","adversaries","floe","uninvited","umiaks","crackup","molested","santiago","contraltos","bethany","exhortations","preferential","gina","processor","beleaguering","fountainhead","politicking","denounces","eats","zodiacs","lubricated","prisoning","chautauqua","apparently","apiaries","lawrence","ellis","vampired","falsifiable","shaker","impecuniousness","maurice","vaginas","fran","cobain","angkor","discernment","numbs","bridges","novelette","renumbering","multiplicand","gluey","tots","garment","outran","disrespects","chino","pennsylvania","puff","chilly","roosted","fuses","concede","unimplemented","misogynist","disheveling","wiggler","penciling","storage","thoroughbreds","copiously","unidentifiable","warpaths","detriments","wantoning","welling","philosophizes","proprietorship","crumbliest","forgather","hemlocks","evangeline","abelson","extant","hijacking","repelling","stockholder","rebuking","stagnates","mechanization","shenyang","obeisance","english","erythrocyte","marring","regenerated","spinster","pest","forgathered","projectionist","match","smolder","rhinos","libretti","astutely","recuperates","outsources","vole","maestros","viewers","imprecision","astrophysicist","aristotelian","impressing","picnicked","minimalism","commas","ladled","gobbles","aborts","ahem","lira","surreptitious","corpses","london","hallucination","hendricks","traumata","anchovy","medication","reexamine","stabilization","jackboot","insular","floated","silkier","entertains","barren","savvier","volatile","amethysts","feuds","cheddar","cogs","trinities","underpasses","whoopee","cult","housing","fussbudgets","laminated","regress","boeotian","fugitive","anthers","nebraska","torch","declassify","tijuana","badges","cohan","stylish","formosan","lifestyles","impresario","love","errata","teletypewriters","resembled","cork","weaver","darlene","preoccupied","cage","faun","reclassifies","confinements","evolution","jayne","syndicate","soaping","provincials","regional","squabble","apricot","totes","herbart","beards","carpetbagged","assignable","henpecks","coating","amplified","insulation","smooths","parliament","sahara","bursitis","lingos","wherewithal","inoffensively","overcrowds","bhutan","disarrange","zippy","flosses","parnell","erratas","sidings","clapboards","confederated","palliative","wirelesses","etruscans","neonates","clayey","vaccinating","peskiest","liable","bibliographical","squidded","hausdorff","lumberyard","blythe","pillions","fiddlesticks","sarong","scarfed","reformer","gunrunning","sweaters","entreats","wicca","tennis","quilt","canisters","frankincense","unbar","neighed","cicadas","bighorns","tittles","dimaggio","costuming","judas","paints","pastorals","carib","glamored","cantering","demotes","currying","excommunicating","thwarting","freebase","niagara","fortification","buttercups","survey","barracudas"]
显示该错误。
我是 python 的新手，所以我无法通过它。谢谢:)
你的代码似乎有一些问题。
if m not in m:这一行没有多大意义...strs.remove(j) 永远不要在迭代列表时从列表中删除，否则会发生坏事- 您正在将每个字符串与其他字符串进行比较，包括它本身
因此，对于您的 ["eat", "tea", "tan", "ate", "nat", "bat"] 示例，您的代码 returns [['eat', 'eat', 'ate'], ['tan', 'tan'], ['bat', 'bat']]
关于性能，最大的问题似乎是每次将字符串与任何其他字符串进行比较时都对字符串进行排序，即总共对 n2 进行排序次！相反，我建议您使用字典将字符串映射到它们的排序版本。
def groupAnagrams(strs):
res = {}
for s in strs:
res.setdefault(''.join(sorted(s)), []).append(s)
return res.values()
示例的输出是 [['tan', 'nat'], ['bat'], ['eat', 'tea', 'ate']]
你可以这样做。在这里，我对每个单词进行哈希处理并制作单词映射。具有相同哈希值的单词是变位词。
import collections
def sort_prehash(word):
return ''.join(sorted(word))
def group_anagrams(words, hash_function):
result = {}
for w in words:
s = hash_function(w.lower())
if s in result:
result[s] |= {w}
else:
result[s] = {w}
return result.values()
orig = ["eat", "tea", "tan", "ate", "nat", "bat"]
print group_anagrams(orig, sort_prehash)
class Solution:
# @param {string[]} strs
# @return {string[][]}
def isAnagram(self, s, t):
s1 = [];s2 = []
s1[:0] = s
s2[:0] = t
s1.sort();s2.sort()
if s1 == s2:
return True
else:
return False
def groupAnagrams(self, strs):
l=[]
for i in strs:
m=[]
if m not in m:
m.append(i)
for j in strs:
if self.isAnagram(i,j)==True:
m.append(j)
strs.remove(j)
l.append(m)
return l
上面的代码当输入：
["shuffled","lacquered","efficacious","michigander","corruptness","internals","converter","speeds","rebellion","transceivers","electroencephalogram","crematories","bespoken","complainant","flotations","nev","blindfolding","corresponds","optionally","aggravating","gratifying","healthfulness","characterizing","dole","fantasies","bulks","responsibly","exploiting","confluences","header","dunno","saddam","adulate","spoken","bargained","funiculars","enlargements","mastered","expended","zambians","muggiest","riveted","junketing","shrewish","issachar","wallpapered","bridges","efficacious","cogitation","parabola","inheres","song","chock","surfing","windy","richer","shields","rehash","autobiographical","idiotic","discipline","keyword","proliferation","hollower","exposing","britain","fred","salarying","misplaying","gallbladder","czechoslovakia","burying","deprivation","lubricated","androids","hurtle","kitty","attach","subsidies","tumbled","unseemliest","impelling","surmise","blundered","etching","stuccoes","windiest","monorail","raided","comedians","theodora","muhammadans","sillies","unlocking","lubricating","desperados","vine","purposeless","calmest","loopy","confluences","clings","today","mountaineer","son","axiomatic","thur","ideograph","document","rudolf","joviality","crystals","moodiest","footprints","net","taney","crane","psycho","quantified","aisle","aimee","vegetarianism","canes","twining","butler","transporters","cohere","wilts","outlines","imbecile","passages","godunov","sunken","maneuvers","papyruses","slowed","residuals","tarpaulins","devour","callus","aldebaran","wraiths","outplay","psychoanalyst","flicking","congealing","unsteadier","smoother","bavarian","savvy","wino","tortola","stiflings","deprecation","iguassu","surnames","chit","fraud","strong","camel","undulate","jiggling","lars","singsonging","canny","someway","overtaken","sonja","rapacity","scotch","discus","spill","boated","americanized","phoneyed","nonprofessional","excessive","nuisance","haddock","fared","jibes","lintels","nurturing","falls","testimonial","pluralism","cookeries","cocksure","cassock","appraiser","contingent","barbarous","shoo","groundings","tulsa","hughes","fiver","taces","compatriot","cockpit","sepoy","naughties","topeka","decadents","rangers","topaz","kr","accoladed","palmed","jackknifes","overbore","blintze","shari","corroborations","mortgagees","tylenol","rockies","caesar","estimations","disconnects","coordinating","satinwood","octopus","smithsonian","dustiness","subscript","compacting","sanctuary","restarting","palmist","johnie","winos","conurbations","contrived","crumby","demavend","blooding","electrodes","composed","wheres","clements","ululate","basketball","cattlemen","callus","toolboxes","harelips","garaged","fuller","stubborn","scald","devotion","revolvers","kernels","lean","adversaries","floe","uninvited","umiaks","crackup","molested","santiago","contraltos","bethany","exhortations","preferential","gina","processor","beleaguering","fountainhead","politicking","denounces","eats","zodiacs","lubricated","prisoning","chautauqua","apparently","apiaries","lawrence","ellis","vampired","falsifiable","shaker","impecuniousness","maurice","vaginas","fran","cobain","angkor","discernment","numbs","bridges","novelette","renumbering","multiplicand","gluey","tots","garment","outran","disrespects","chino","pennsylvania","puff","chilly","roosted","fuses","concede","unimplemented","misogynist","disheveling","wiggler","penciling","storage","thoroughbreds","copiously","unidentifiable","warpaths","detriments","wantoning","welling","philosophizes","proprietorship","crumbliest","forgather","hemlocks","evangeline","abelson","extant","hijacking","repelling","stockholder","rebuking","stagnates","mechanization","shenyang","obeisance","english","erythrocyte","marring","regenerated","spinster","pest","forgathered","projectionist","match","smolder","rhinos","libretti","astutely","recuperates","outsources","vole","maestros","viewers","imprecision","astrophysicist","aristotelian","impressing","picnicked","minimalism","commas","ladled","gobbles","aborts","ahem","lira","surreptitious","corpses","london","hallucination","hendricks","traumata","anchovy","medication","reexamine","stabilization","jackboot","insular","floated","silkier","entertains","barren","savvier","volatile","amethysts","feuds","cheddar","cogs","trinities","underpasses","whoopee","cult","housing","fussbudgets","laminated","regress","boeotian","fugitive","anthers","nebraska","torch","declassify","tijuana","badges","cohan","stylish","formosan","lifestyles","impresario","love","errata","teletypewriters","resembled","cork","weaver","darlene","preoccupied","cage","faun","reclassifies","confinements","evolution","jayne","syndicate","soaping","provincials","regional","squabble","apricot","totes","herbart","beards","carpetbagged","assignable","henpecks","coating","amplified","insulation","smooths","parliament","sahara","bursitis","lingos","wherewithal","inoffensively","overcrowds","bhutan","disarrange","zippy","flosses","parnell","erratas","sidings","clapboards","confederated","palliative","wirelesses","etruscans","neonates","clayey","vaccinating","peskiest","liable","bibliographical","squidded","hausdorff","lumberyard","blythe","pillions","fiddlesticks","sarong","scarfed","reformer","gunrunning","sweaters","entreats","wicca","tennis","quilt","canisters","frankincense","unbar","neighed","cicadas","bighorns","tittles","dimaggio","costuming","judas","paints","pastorals","carib","glamored","cantering","demotes","currying","excommunicating","thwarting","freebase","niagara","fortification","buttercups","survey","barracudas"]
显示该错误。 我是 python 的新手，所以我无法通过它。谢谢:)
你的代码似乎有一些问题。
if m not in m:这一行没有多大意义...strs.remove(j)永远不要在迭代列表时从列表中删除，否则会发生坏事- 您正在将每个字符串与其他字符串进行比较，包括它本身
因此，对于您的 ["eat", "tea", "tan", "ate", "nat", "bat"] 示例，您的代码 returns [['eat', 'eat', 'ate'], ['tan', 'tan'], ['bat', 'bat']]
关于性能，最大的问题似乎是每次将字符串与任何其他字符串进行比较时都对字符串进行排序，即总共对 n2 进行排序次！相反，我建议您使用字典将字符串映射到它们的排序版本。
def groupAnagrams(strs):
res = {}
for s in strs:
res.setdefault(''.join(sorted(s)), []).append(s)
return res.values()
示例的输出是 [['tan', 'nat'], ['bat'], ['eat', 'tea', 'ate']]
你可以这样做。在这里，我对每个单词进行哈希处理并制作单词映射。具有相同哈希值的单词是变位词。
import collections
def sort_prehash(word):
return ''.join(sorted(word))
def group_anagrams(words, hash_function):
result = {}
for w in words:
s = hash_function(w.lower())
if s in result:
result[s] |= {w}
else:
result[s] = {w}
return result.values()
orig = ["eat", "tea", "tan", "ate", "nat", "bat"]
print group_anagrams(orig, sort_prehash)