# Here is my Accepted python solution.

• Code use bfs to search all graph node, and it will cut the visited node.
This solution cost 2840ms, I think the limit time is 3000ms. so luck.

``````class Solution:
# @param start, a string
# @param end, a string
# @param words, a set of string
# @return a list of lists of string
pathes=[];
graphNodes={};
queue=[(start,0,[])];
minPath=0;
nodeShortPathCache={};

while(len(queue)>0):
node,dis,path=queue.pop(0);

if(node not in graphNodes):
graphNodes[node]=[];
for i in range(len(node)):
for j in 'abcdefghijklmnopqrstuvwxyz':
if(j==node[i]):
continue;
newNode = node[0:i] + j + node[i + 1:]
if(newNode in words):
graphNodes[node].append(newNode);

if(node in nodeShortPathCache):
if(dis>nodeShortPathCache[node]):
continue;
else:
nodeShortPathCache[node]=dis;
if(node==end):
newpath=list(path);
newpath.append(node);
if(minPath==0):
minPath=dis;
if(dis==minPath):
pathes.append(newpath);
else:
newpath=list(path);
newpath.append(node);
for childNode in graphNodes[node]:
if(childNode in nodeShortPathCache):
if(dis+1>nodeShortPathCache[childNode]):
continue;
queue.append((childNode,dis+1,newpath));
return pathes;``````

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