Word Ladder Puzzle

Construct a graph to solve it with BFS

Assumption

  • all words have the same length

Approach

  • vertex -> word
  • edge : if 2 words are different by only one letter
  • undirected, unweighted

But compare each pair is too much. We should use bucket.

like .ope, p.pe, po.e, pop.

pic

def buildGraph(wordFile):
    d = {}
    g = Graph()
    wFile = open(wordFile, 'r')
    for line in wFile:
        word = line[:-1]
        for i in range(len(word)):
            pattern = word[:i] + '.' + word[i+1:]
            if pattern in d:
                d[pattern].append(word)
            else:
                d[pattern] = word

    for pattern in d.keys():
        # bi-directed
        for word1 in d[pattern]:
            for word2 in d[pattern]:
                if word1 != wor2:
                    g.addEdge(word1, word2)

    return g

Solve the word ladder problem

  • BFS
  • keep a parent record

BFS use queue to implement

get the pathes is just like a permutation from end word.

Run time

O(V+E)