My own code exceeds time limit and I run the Last executed input on my computer which takes about 3~4 seconds. Then I found the following code which is accepted. The strange thing is I run this program on the same test case and it took about 10 seconds.
class Solution: # @param start, a string # @param end, a string # @param dict, a set of string # @return an integer def ladderLength(self, start, end, dict): if start == end: return 1 all_chars = map(chr, xrange(ord('a'), ord('z') + 1)) visited = set() bfs = [start, None] # at which distance the following to-be-processed nodes are distance = 2 while len(bfs) > 1: word = bfs.pop(0) if word is None: distance += 1 bfs.append(None) continue for i in xrange(len(word)): for char in all_chars: new_word = word[:i] + char + word[i + 1:] if new_word == end: return distance if new_word in dict and new_word not in visited: bfs.append(new_word) visited.add(new_word) return 0
And here below is my code. My TLE solution works way faster than the code above on my own computer, but I don't know why it turns out to be slow on the OJ system.
# -*- coding:utf-8 -*- # Return True if the two strings have one different character def oneDiff(stra, strb): count = 0 for i in range(len(stra)): if stra[i] != strb[i]: count += 1 if count > 1: return False if count != 1: return False return True # Binary search # Return True if samp is in dic def isIn(samp, dic, first=None, last=None): if first == None: first = 0 if last == None: last = len(dic) - 1 if first > last: return False m = (first + last) / 2 if samp == dic[m]: return True elif samp < dic[m]: return isIn(samp, dic, first, m-1) else: return isIn(samp, dic, m+1, last) # Generate a list of words that are one character different with sample def diffList(sample): alist =  for i in range(len(sample)): c = ord(sample[i]) - 97 for j in range(26): if j != c: mtstr = sample[:i] + chr(j + 97) + sample[i+1:] alist.append(mtstr) return alist class Solution: # @param start, a string # @param end, a string # @param dict, a set of string # @return an integer def ladderLength(self, start, end, dic): dic = sorted(dic) # sort the dictionary path = collections.deque() visit = set() for it in diffList(start): # put the starting points into the queue if isIn(it,dic): path.appendleft([it, 2]) visit.add(it) while len(path) > 0: # [midway, distence] = path.pop() if oneDiff(midway, end): return distence + 1 for item in diffList(midway): if item in visit or not isIn(item,dic): continue else: path.appendleft([item, distence+1]) visit.add(item) return 0
This is the test case which I failed on.
dict is a 'set' object, and when you call 'item in dict', it will be searched by hash table, which is faster (O(1)) than binary search (O(log n)).
BTW, there are so many function calls of chr() and list.append() in your diffList() function. But in the simple code, he predefine the 'all_chars' list and use 'for each' in every while loop, which is faster.