word_ladder.py

import string

class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return an integer
    def ladderLength(self, start, end, dict):
        dict += [end]

        def next_edges(word):
            edges = []
            word_chars = list(word)
            for i in range(len(word)):
                new_word_chars = list(word_chars)
                for c in string.lowercase:
                    new_word_chars[i] = c
                    new_word = "".join(new_word_chars)
                    if new_word in dict and new_word not in edges:
                        edges += [new_word]
            return edges
        
        visited = set()
        queue = set([start])
        d = 1
        while len(queue) > 0:
            #print queue
            new_queue = set()
            for cur in queue:
                if cur == end:
                    return d
                visited.add(cur)
                new_queue |= {e for e in next_edges(cur) if e not in visited}
            queue = new_queue
            d += 1
            
        return 0