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


  • 1
    V

    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
    
    
    def findLadders(self, start, end, wordDict):
        if self.isTransformable(start, end):
            return[[start,end]]
        startTable = [[start]]
        endTable = [[end]]
        wordDict.discard(start)
        wordDict.discard(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 []

Log in to reply
 

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