word ladder in python

Question

I'm trying to create a word ladder program in python. I'd like to generate words that are similar to a given word. In c++ or java, I would go through each valid index in the original string, and replace it with each letter in the english alphabet, and see if the result is a valid word. for example (pseudocode)

for (int i = 0; i < word.length(); i++) {
  for (every character c in the alphabet) {
    change the letter of word at index i to be c. 
    if the result is a valid word, store it in a list of similar words
  }
}

.

However, this doesn't seem like a very "python" way of doing things. How would I approach this problem in python?

Answer 1

A generator of similar words (taking a predicate, i.e. a function argument which returns true or false, to check whether a word is valid) seems a reasonable first step:

import string

def allsimilar(word, valid):
  wl = list(word)
  for i, c in enumerate(wl):
    for x in string.ascii_lowercase:
      if x == c: continue
      wl[i] = x
      nw = ''.join(wl)
      if valid(nw): yield nw
    wl[i] = c

If you want the list, list(allsimilar(word, valid)) will of course build it for you.

Alternatively, you could omit wl and build the new word directly as

nw = word[:i] + x + word[i+1:]

but, without having timed it carefully, I suspect that might be slower.

One small possible optimization would be to also import array and then use

  wl = array.array('c', word)

instead of list(word).