Share my two Python solutions: a very concise one (12 lines, ~160ms) and an optimized solution(~100ms)

• The idea behind the first solution is to use character flopping plus bidirectional BFS. Use set operations as much as possible.

class Solution:
# @param {string} beginWord
# @param {string} endWord
# @param {set<string>} wordDict
# @return {integer}
length = 2
front, back = set([beginWord]), set([endWord])
while front:
# generate all valid transformations
front = wordDict & (set(word[:index] + ch + word[index+1:] for word in front
for index in range(len(beginWord)) for ch in 'abcdefghijklmnopqrstuvwxyz'))
if front & back:
# there are common elements in front and back, done
return length
length += 1
if len(front) > len(back):
# swap front and back for better performance (fewer choices in generating nextSet)
front, back = back, front
# remove transformations from wordDict to avoid cycle
wordDict -= front
return 0

The optimizations:

-- Generating next set

An alternative is to immediately add a candidate to next set if it is in the dictionary.

Another way to generate next set: for each word in the current set, check if a word in the dictionary can be transformed to it. If it can, add it to the next set. The time complexity of the two methods is analyzed below, assuming word length is L, size of current set and dictionary are M and N, respectively.

a. character flopping:

Loop over current set, character of word, alphabet, the flopping itself is O(L). Time complexity is O(26ML^2)

b. verify transformation:

Loop over current set, dictionary, character of word. Time complexity is O(MNL)

For b) to be faster, the switching point is N = 26L. This scale can be adjusted.

Since the size of dictionary shrinks during the process, it is beneficial to switch to b) in the late stage, or use it for a small dictionary.

-- Removing current word set from dictionary

It seems natural to use difference_update for this job since size of dictionary is bigger than that of current word set. But is it so? Note that here we are sure that every word in current set does exist in the dictionary.

a. S.difference_update(T) or S -= T

For every key (entry) in T, if it is in S, remove it from T. There are len(T) removes and len(T) peeks.

b. S.difference(T) or S - T

Create a new empty set. For every key (entry) in S, if it is not in T, add it to new set. There are len(S)-len(T) adds and len(S) peeks.

If the sizes of current word set and dictionary are close, using difference_update means we will remove almost everything from dictionary. If we use difference, only a handful of adds. I use size of dictionary is twice that of current word set as the switching point. This threshold can be adjusted too.
The following optimized code takes ~100ms.

class Solution:
# @param {string} beginWord
# @param {string} endWord
# @param {set<string>} wordDict
# @return {integer}
def generateNextSet1(current, wordDict, wordLen):
nextSet = set()
for word in current:
for index in range(wordLen):
for ch in 'abcdefghijklmnopqrstuvwxyz':
nextWord = word[:index] + ch + word[index+1:]
if nextWord in wordDict:
return nextSet

def generateNextSet2(current, wordDict):
nextSet = set()
for word in current:
for nextWord in wordDict:
index = 0
try:
while word[index] == nextWord[index]:
index += 1
if word[index+1:] == nextWord[index+1:]:
except:
continue
return nextSet

steps, wordLen = 2, len(beginWord)
front, back = set([beginWord]), set([endWord])
switchThreshold = 26*wordLen
while front:
# get all valid transformations
if len(wordDict) >= switchThreshold:
front = generateNextSet1(front, wordDict, wordLen)
else:
front = generateNextSet2(front, wordDict)
if front & back:
# there are common elements in front and back, done
return steps
steps += 1
if len(front) >= len(back):
# swap front and back for better performance (smaller nextSet)
front, back = back, front
# remove transformations from wordDict to avoid cycles
if (len(wordDict)>>1) >= len(front):
# s.difference_update(t): O(len(t))
wordDict -= front
else:
# s.difference(t): O(len(s))
wordDict = wordDict - front
return 0

• Fantastic solution, thanks to you I learned the bidirectional BFS.
But you solution can't handle input like a,c [b]
Because the updated "front" set won't have a overlap with "back" set, this can happen if the "set" didn't move inside the dictionary.
I found this issue when I was thinking why there is no "wordDict.discard(endWord)"
Here is my improvement upon your solution:

class Solution:
# @param {string} beginWord
# @param {string} endWord
# @param {set<string>} wordDict
# @return {integer}
front, back=set([beginWord]), set([endWord])
length=2
width=len(beginWord)
charSet=list(string.lowercase)
while front:
newFront=set()
for phrase in front:
for i in xrange(width):
for c in charSet:
nw=phrase[:i]+c+phrase[i+1:]
if nw in back:
return length
if nw in wordDict:
front=newFront
if len(front)>len(back):
front,back=back,front
wordDict-=front
length+=1
return 0

• Yeah, my solution will fail the a, c, [b] case. But I have found that Leetcode puts both startWord and endWord into dictionary :). Otherwise I can add endWord into the dictionary at the beginning.

• change: charSet=list(string.lowercase)
to: charSet='abcdefghijklmnopqrstuvwxyz'

change: for i in xrange(width):
to: for i in range(width):

so that it can run on python 3

• if len(front)>len(back):
front,back=back,front

this is brilliant!

• Python3 will optimize range to behave the same as xrange in python2.X, and delete key word xrange, So range will be more friendly to python3, not xrange.

• i think it can be:

if nw in wordDict:

to save some time?

• @coolgod Yes! so we won't step into this word later. Thanks!

• here is my easy-to-understand code:

import string
class Solution(object):
front = {beginWord}
back = {endWord}
dist = 1
wordList = set(wordList)
word_len = len(beginWord)
while front:
dist += 1
next_front = set()
for word in front:
for i in range(word_len):
for c in string.lowercase:
if c != word[i]:
new_word = word[:i]+c+word[i+1:]
if new_word in back:
return dist
if new_word in wordList:
wordList.remove(new_word)
front = next_front
if len(back)<len(front):
front, back = back, front
return 0

• For endWord corner case.

class Solution(object):
if endWord not in wordDict:
return 0
length = 2
front, back = set([beginWord]), set([endWord])
wordDict = set(wordDict)
while front:
# generate all valid transformations
front = wordDict & (set(word[:index] + ch + word[index+1:] for word in front
for index in range(len(beginWord)) for ch in string.ascii_lowercase))
if front & back:
# there are common elements in front and back, done
return length
length += 1
if len(front) > len(back):
# swap front and back for better performance (fewer choices in generating nextSet)
front, back = back, front
# remove transformations from wordDict to avoid cycle
wordDict -= front
return 0

• @dasheng2 Why when test case is "hit" "cog" ["hot","dot","dog","lot","log"], 5 is outputted, but 0 is expected?

• @TianQ @dasheng2 Why when test case is "hit" "cog" ["hot","dot","dog","lot","log"], 5 is outputted, but 0 is expected? same issue with some other solutions in this post.

• @Chengcheng.Pei @dasheng2
"cog", the endWord is a transformed word, but not in wordList, so return 0. Check this corner at the beginning:

if endWord not in wordList:
return 0

• a. S.difference_update(T) or S -= T
For every key (entry) in T, if it is in S, remove it from T. There are len(T) removes and len(T) peeks.

Excellent analysis, just one typo: should be "remove it from S".

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