Always Return An Answer
Whenever you're writing an algorithm, it should return the answer. Not print and return, not just print. Just return. If you want to print, you can always write print some_algo(...).
is_diff_one
We can write this a little cleaner. There is a zip() function in the Python standard library that can walk multiple iterables at once. (In Python 2.7, we should use itertools.izip() since that won't generate a whole list up front). The advantage here is that we can write:
count = 0
for a, b in zip(str1, str2):
if a != b:
count += 1
if count > 1:
# quit early
return False
# in case we're equal
return count == 1
Try to avoid patterns like:
if expr:
return True
return False
That's the same as return expr
Backtracking
This line:
potential_ans[:-1]
doesn't actually do anything. It will return a slice of potential_ans, but it doesn't actually modify it. What you wanted to do was
potential_ans.pop()
But this is error-prone (and relies on global state). Instead of modifying potential_ans, what we can do is provide a new object to each recursive instantiation. This leads me to...
Your algorithm
Now, you want this to be entirely self-contained. You're right in wanting to avoid global variables - and you have most of the right idea in that we want to recursively call down with the next word. The one change is the last argument. count isn't really meaningful here. What you want instead is the path you've come so far:
def transform(english_words, start, end, cur_path):
if start == end:
return [cur_path]
That way, our path is local rather than global. Then we just walk the rest of the words as you're doing:
results = []
for w in english_words:
if is_diff_one(w, start) and w not in cur_path:
solutions = transform(english_words, w, end, cur_path + [w])
results.extend(solutions)
return results
Note that I'm changing your return type from list to list of lists. Now this will return a list of all the possible transformation lists.
Of course, we'd need a sensible default cur_path. Let's avoid the user having to come up with one:
def transform(english_words, start, end, cur_path=None):
if cur_path is None:
cur_path = [start]