# Why can this simple code be accepted?

• 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
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)

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
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])

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])
return 0
``````

This is the test case which I failed on.
http://www.mediafire.com/view/l6i4favodvmkibe/testcase.txt

• 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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.