# 129 ms Python solution using char flipping and searching from both end.

• class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return a list of lists of string

``````def isTransformable (self, s,t):
n=0
for i in xrange(len(s)):
if s[i] != t[i]:
n+=1
if n>1:
return False
return n==1

if self.isTransformable(start, end):
return[[start,end]]
startTable = [[start]]
endTable = [[end]]
startCount = 1
endCount = 1
startDict = wordDict.copy()
endDict = wordDict.copy()
temp=[]
tempendTable=[]
startTableReachEnd = False

while (startTable[-1] and endTable[-1]):

count = 0
if len(startTable[-1])*len(startDict) <= len(endTable[-1])*len(endDict) and not startTableReachEnd:

tempstartTable = []
for word in startTable[-1]:

if self.isTransformable(word, end):
startTableReachEnd = True

for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
nextWord = word[:i] + c + word[i+1:]
if nextWord in startDict:
count = 1
tempstartTable.append(nextWord)
startDict.remove(nextWord)
if count ==0 and not startTableReachEnd:
return []

if startTableReachEnd:

tempstartTable =startTable[-1][:]
continue

startCount += count
startTable.append(tempstartTable)

else:

tempendTable = []
for word in endTable[-1]:

for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
nextWord = word[:i] + c + word[i+1:]
if nextWord in endDict:
count = 1
tempendTable.append(nextWord)
endDict.remove(nextWord)
if count ==0:
return []
endCount += count
endTable.append(tempendTable)

temp = list(set(tempstartTable) & set(tempendTable))

if temp:

if temp == [start]:
return [[start, end]]
ans=[]
for i in temp:
ans.append([i])

startTable.pop()
endTable.pop()

while startTable:
tempstartTable = startTable.pop()
tempans = []
for i in xrange(len(ans)):
for j in tempstartTable:
if self.isTransformable(ans[i][0], j):
tempans.append([j]+ans[i])
ans = tempans[:]

while endTable:
tempendTable = endTable.pop()
tempans = []
for i in xrange(len(ans)):
for j in tempendTable:
if self.isTransformable(ans[i][-1], j):
tempans.append(ans[i]+[j])
ans = tempans[:]

return ans
return []``````

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