Here is my Accepted python solution.


  • 1
    L

    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
    def findLadders(self, start, end, words):
        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;

Log in to reply
 

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