Word ladder Timi


  • 0
    S
    class Solution:
        # @param start, a string
        # @param end, a string
        # @param dict, a set of string
        # @return an integer
        def ladderLength(self, start, end, d):
            if start == end:
                return 0
            if not d:
                return 0
            words = [start]
            visited = [start]
            prevNumOfNodes = 1
            currNumOfNodes = 0
            level = 0
            allLetters = "abcdefghijklmnopqrstuvwxyz"
            while words:
                curr = words.pop(0)
                prevNumOfNodes = prevNumOfNodes - 1
                if curr == end:
                    return level + 1
                for i,l in enumerate(curr):
                    for j in allLetters:
                        if l!=j:
                            prevCurr = curr
                            curr = curr[:i] + j + curr[i+1:]
                            if curr not in visited and curr in d:
                                visited.append(curr)
                                words.append(curr)
                                currNumOfNodes = currNumOfNodes + 1
                            curr = prevCurr
                if prevNumOfNodes == 0:
                    prevNumOfNodes = currNumOfNodes
                    currNumOfNodes = 0
                    level = level + 1
            return 0

Log in to reply
 

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