solves a word ladder given a dictionary

word_ladder.py

from string import ascii_lowercase as alphabet

d = {"dog","dig", "din", "dag","fog", 
     "god", "fig", "ape", "dot", "got",
     "bog", "bag","bat","cat"
     }

def transform(w1, w2):
    frontier = [[w1]]
    explored = set()
    while(len(frontier) > 0):
        curr_path = frontier.pop(0)
        word = curr_path[-1]
        if word == w2:
            return curr_path
        else:
            explored.add(word)
            neighbors = []
            for i in range(len(word)):
                for char in alphabet:
                    new_word = word[:i] + char + word[i+1:]
                    if new_word == w1:
                        continue
                    elif is_word(new_word) and new_word not in explored:
                        neighbors.append(curr_path[:] + [new_word])
            for n in neighbors:
                frontier.append(n)
    return w1

def is_word(w):
    return w in d

def main():
    print transform("bob","cat")

if __name__ == "__main__":
    main()