# A Python solution which is easy to understand

• Inspired by Peter Norvig's great article: How to Write a Spelling Corrector.

Basicly, I intersect all the possible replaces of edit distance 1 of a word with the remaining wordDict to search for the next batch of possible transforms until endWord is reached or there are no more moves.
Python's set() is absolutely an ideal tool for this job, translation from idea to code is direct, smooth and clear by utilizing it.

``````import string
class Solution:
# @param beginWord, a string
# @param endWord, a string
# @param wordDict, a set<string>
# @return an integer

def edit_distance1_set(word):
return set(
a + c + b[1:]
for a, b in [(word[:i], word[i:]) for i in range(len(word) + 1)]
for c in string.lowercase if b) - set([word])

def distance(wa, wb):
count = 0
for i in range(len(wa)):
if wa[i] != wb[i]:
count += 1
return count

def next_words(word, lst):
"""return a candidates list of word's next transform"""
return edit_distance1_set(word).intersection(lst)

if not isinstance(wordDict, set):
wordDict = set(wordDict)
if distance(beginWord, endWord) == 1:
return 2

landing_zone = next_words(endWord, wordDict)

if not landing_zone:
return 0
explore = set([beginWord])
remain = wordDict - explore
depth = 2
while not (landing_zone.intersection(explore)):
# print explore
if not remain:
return 0
# print 'depth:{}, '.format(depth), explore
old_explore = explore
explore = set()
for w in old_explore:
explore.update(next_words(w, remain))
if not explore:
return 0
remain.difference_update(explore)
depth += 1
# print explore, landing_zone
return depth
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.