• 19.2%

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

UPDATE (2017/1/20):

The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

https://discuss.leetcode.com/topic/16983/easy-76ms-c-solution-using-bfs

Easy 76ms C++ Solution using BFS

Well, this problem has a nice BFS structure.

Let’s see the example in the problem statement.

Since only one letter can be changed at a time, if we start from “hit”, we can only change to those words which have only one different letter from it, like “hot”. Putting in graph-theoretic terms, we can say that “hot” is a neighbor of “hit”.

The idea is simpy to begin from start, then visit its neighbors, then the non-visited neighbors of its neighbors… Well, this is just the typical BFS structure.

To simplify the problem, we insert end into dict. Once we meet end during the BFS, we know we have found the answer. We maintain a variable dist for the current distance of the transformation and update it by dist++ after we finish a round of BFS search (note that it should fit the definition of the distance in the problem statement). Also, to avoid visiting a word for more than once, we erase it from dict once it is visited.

The code is as follows.

The above code can still be speeded up if we also begin from end. Once we meet the same word from start and end, we know we are done. This link provides a nice two-end search solution. I rewrite the code below for better readability. Note that the use of two pointers phead and ptail save a lot of time. At each round of BFS, depending on the relative size of head and tail, we point phead to the smaller set to reduce the running time.

https://discuss.leetcode.com/topic/10372/share-my-two-end-bfs-in-c-80ms

Share my two-end BFS in C++ 80ms.

https://discuss.leetcode.com/topic/43246/simple-to-understand-python-solution-using-list-preprocessing-and-bfs-beats-95

Simple to understand Python solution using list preprocessing and BFS, beats 95%

https://discuss.leetcode.com/topic/42623/compact-python-solution

Compact Python solution

172ms, 78.99%, June.24th, 2016

https://leetcode.com/discuss/48083/share-python-solutions-concise-160ms-optimized-solution-100ms

https://discuss.leetcode.com/topic/20965/java-solution-using-dijkstra-s-algorithm-with-explanation

Java Solution using Dijkstra’s algorithm, with explanation

Basically I keep two sets of words, one set reached that represents the borders that have been reached with “distance” steps; another set wordDict that has not been reached. In the while loop, for each word in the reached set, I give all variations and check if it matches anything from wordDict, if it has a match, I add that word into toAdd set, which will be my “reached” set in the next loop, and remove the word from wordDict because I already reached it in this step. And at the end of while loop, I check the size of toAdd, which means that if I can’t reach any new String from wordDict, I won’t be able to reach the endWord, then just return 0. Finally if the endWord is in reached set, I return the current steps “distance”.

The idea is that reached always contain only the ones we just reached in the last step, and wordDict always contain the ones that haven’t been reached. This is pretty much what Dijkstra’s algorithm does, or you can see this as some variation of BFS.

ps: I get TLE at the first two submissions, because when I check if wordDict has any matches with reached set, I use two for loops and determine if any pair of words differ by one. That’s a huge slow-down because it’ll takes m (size of reached) n (size of wordDict) l (length of words) time, while in this solution, it takes 26 l m time. So when n is huge, this solution will be (n/26) times faster.

https://discuss.leetcode.com/topic/20965/java-solution-using-dijkstra-s-algorithm-with-explanation/2

I think we can use a queue to replace the reached set, by which we can avoid duplicate check?

https://discuss.leetcode.com/topic/29303/two-end-bfs-in-java-31ms

Two-end BFS in Java 31ms.

Modified from Share my two-end BFS in C++ 80ms.

https://discuss.leetcode.com/topic/17890/another-accepted-java-solution-bfs

Another accepted Java solution (BFS)