A Python solution based on char flipping

  • 3
    class Solution:
        # @param start, a string
        # @param end, a string
        # @param dict, a set of string
        # @return an integer
        # 5:35
        def ladderLength(self, start, end, dict):
            table = {start: 1}
            while table:
                temptable = table.copy()
                for word, count in temptable.viewitems():
                    del table[word]
                    if self.hasLadder(word, end):
                        return count + 1
                    for i in range(len(word)):
                        for c in 'abcdefghijklmnopqrstuvwxyz':
                            nextWord = word[:i] + c + word[i+1:]
                            if nextWord in dict:
                                table[nextWord] = count + 1
            return 0
        def hasLadder(self, src, target):
            diff = 0
            for i in range(len(src)):
                if src[i] != target[i]:
                    diff += 1
            if diff == 1:
                return True
                return False

Log in to reply

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