120ms Python solution based on char flipping and double bfs


  • 0
    V

    class Solution:
    # @param beginWord, a string
    # @param endWord, a string
    # @param wordDict, a set<string>
    # @return an integer

    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 ladderLength(self, start, end, wordDict):
        startTable = set()
        startTable.add(start)
        endTable = set()
        endTable.add(end)
        startCount = 1
        endCount = 1
        startDict = wordDict.copy()
        endDict = wordDict.copy()
        while startTable and endTable:
            
            count = 0
            if len(startTable)*len(startDict) <= len(endTable)*len(endDict):
                tempstartTable = startTable.copy()
                
                for word in tempstartTable:
                    startTable.remove(word)
    
                    if self.isTransformable(word, end):
                        return startCount + 1
    
                    for i in range(len(word)):
                        for c in 'abcdefghijklmnopqrstuvwxyz':
                            nextWord = word[:i] + c + word[i+1:]
                            if nextWord in startDict:
                                count = 1
                                startTable.add(nextWord)
                                startDict.remove(nextWord)
                startCount += count
            else:
                tempendTable = endTable.copy()
                for word in tempendTable:
                    endTable.remove(word)
    
                    if self.isTransformable(word, start):
                        return endCount + 1
    
                    for i in range(len(word)):
                        for c in 'abcdefghijklmnopqrstuvwxyz':
                            nextWord = word[:i] + c + word[i+1:]
                            if nextWord in endDict:
                                count = 1
                                endTable.add(nextWord)
                                endDict.remove(nextWord)
                endCount += count
            
            if startTable & endTable:
                return startCount + endCount - 1
    
        return 0

  • 0
    K

    Great solution, damn fast.


Log in to reply
 

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