x****g
发帖数: 39 | 1 import string
class Solution(object):
def ladderLength(self, beginWord, endWord, wordDict):
"""
:type beginWord: str
:type endWord: str
:type wordDict: Set[str]
:rtype: int
"""
transformation = [beginWord]
wordDict.remove(beginWord)
length = 1
while transformation:
for i in range(len(transformation)):
fromWord = transformation.pop(0)
for i in range(len(fromWord)):
c = fromWord[i]
for char in string.lowercase:
if char != c:
new_word = '%s%s%s' % (fromWord[:i], char,
fromWord[i+1:])
if new_word in wordDict:
transformation.append(new_word)
wordDict.remove(new_word)
if new_word == endWord:
return length + 1
break
if transformation:
print "transformation=", transformation
length += 1
return 0
"nape", "mild", ["dose","ends","dine","jars","prow","soap","guns","hops","
cray","hove","ella","hour","lens","jive","wiry","earl","mara","part","flue",
"putt","rory","bull","york","ruts","lily","vamp","bask","peer","boat","dens"
,"lyre","jets","wide","rile","boos","down","path","onyx","mows","toke","soto
","dork","nape","mans","loin","jots","male","sits","minn","sale","pets","
hugo","woke","suds","rugs","vole","warp","mite","pews","lips","pals","nigh",
"sulk","vice","clod","iowa","gibe","shad","carl","huns","coot","sera","mils"
,"rose","orly","ford","void","time","eloy","risk","veep","reps","dolt","hens
","tray","melt","rung","rich","saga","lust","yews","rode","many","cods","
rape","last","tile","nosy","take","nope","toni","bank","jock","jody","diss",
"nips","bake","lima","wore","kins","cult","hart","wuss","tale","sing","lake"
,"bogy","wigs","kari","magi","bass","pent","tost","fops","bags","duns","will
","tart","drug","gale","mold","disk","spay","hows","naps","puss","gina","
kara","zorn","boll","cams","boas","rave","sets","lego","hays","judy","chap",
"live","bahs","ohio","nibs","cuts","pups","data","kate","rump","hews","mary"
,"stow","fang","bolt","rues","mesh","mice","rise","rant","dune","jell","laws
","jove","bode","sung","nils","vila","mode","hued","cell","fies","swat","
wags","nate","wist","honk","goth","told","oise","wail","tels","sore","hunk",
"mate","luke","tore","bond","bast","vows","ripe","fond","benz","firs","zeds"
,"wary","baas","wins","pair","tags","cost","woes","buns","lend","bops","code
","eddy","siva","oops","toed","bale","hutu","jolt","rife","darn","tape","
bold","cope","cake","wisp","vats","wave","hems","bill","cord","pert","type",
"kroc","ucla","albs","yoko","silt","pock","drub","puny","fads","mull","pray"
,"mole","talc","east","slay","jamb","mill","dung","jack","lynx","nome","leos
","lade","sana","tike","cali","toge","pled","mile","mass","leon","sloe","
lube","kans","cory","burs","race","toss","mild","tops","maze","city","sadr",
"bays","poet","volt","laze","gold","zuni","shea","gags","fist","ping","pope"
,"cora","yaks","cosy","foci","plan","colo","hume","yowl","craw","pied","toga
","lobs","love","lode","duds","bled","juts","gabs","fink","rock","pant","
wipe","pele","suez","nina","ring","okra","warm","lyle","gape","bead","lead",
"jane","oink","ware","zibo","inns","mope","hang","made","fobs","gamy","fort"
,"peak","gill","dino","dina","tier"]
这个数据在本地
real 0m0.036s
user 0m0.027s
sys 0m0.008s
运行完，为什么是超时呢？ | s*******i
发帖数: 698 | | x****g
发帖数: 39 | 3 真是。更新了 code 成可以过的版本。
【在 s*******i 的大作中提到】
: print忘了删了？
|
|
