Algorithm to transform one word to another through valid words

This can be modelled as a graph problem. You can think of the words as nodes of the graph and two nodes are connected if and only if they are of same length and differ in one char.

You can preprocess the dictionary and create this graph, should look like:

   stack  jack
    |      |
    |      |
   smack  back -- pack -- pick

You can then have a mapping from the word to the node representing the word, for this you can use a hash table, height balanced BST ...

Once you have the above mapping in place, all you have to do is see if there exists a path between the two graph nodes, which can easily be done using BFS or DFS.

So you can summarize the algorithm as:

preprocess the dictionary and create the graph.
Given the two inputs words w1 and w2
if length(w1) != length(w2)
 Not possible to convert
else
 n1 = get_node(w1)
 n2 = get_node(w2)

 if(path_exists(n1,n2))
   Possible and nodes in the path represent intermediary words
 else
   Not possible

Create a graph with each node representing word in the dictionary. Add an edge between two word nodes, if their corresponding words are at edit distance of 1. Then minimum number of transformations required would length of shortest path between source node and destination node.

You could simply use recursive back-tracking but this is far from the most optimal solution.

# Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only
# one letter at a time.  The new word you get in each step must be in the
# dictionary.

# def transform(english_words, start, end):

# transform(english_words, 'damp', 'like')
# ['damp', 'lamp', 'limp', 'lime', 'like']
# ['damp', 'camp', 'came', 'lame', 'lime', 'like']


def is_diff_one(str1, str2):
    if len(str1) != len(str2):
        return False

    count = 0
    for i in range(0, len(str1)):
        if str1[i] != str2[i]:
            count = count + 1

    if count == 1:
        return True

    return False


potential_ans = []


def transform(english_words, start, end, count):
    global potential_ans
    if count == 0:
        count = count + 1
        potential_ans = [start]

    if start == end:
        print potential_ans
        return potential_ans

    for w in english_words:
        if is_diff_one(w, start) and w not in potential_ans:
            potential_ans.append(w)
            transform(english_words, w, end, count)
            potential_ans[:-1]

    return None


english_words = set(['damp', 'camp', 'came', 'lame', 'lime', 'like'])
transform(english_words, 'damp', 'lame', 0)

codaddict's graph approach is valid, though it takes O(n^2) time to build each graph, where n is the number of words of a given length. If that's a problem, you can build a bk-tree much more efficiently, which makes it possible to find all words with a given edit distance (in this case, 1) of a target word.