• 13.7%

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) 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 an empty list 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.

88ms! Accepted c++ solution with two-end BFS. 68ms for Word Ladder and 88ms for Word Ladder II

In order to reduce the running time, we should use two-end BFS to slove the problem.

Accepted 68ms c++ solution for Word Ladder.

Accepted 88ms c++ solution for Word Ladder II.

https://discuss.leetcode.com/topic/40902/clean-but-the-best-submission-68ms-in-c-well-commented

Clean but the best-submission (68ms) in C++, well-commented

https://discuss.leetcode.com/topic/43603/fast-and-clean-python-c-solution-using-double-bfs-beats-98

FAST AND CLEAN Python/C++ Solution using Double BFS, beats 98%

If we know source and destination, we can build the word tree by going forward in one direction and backwards in the other. We stop when we have found that a word in the next level of BFS is in the other level, but first we need to update the tree for the words in the current level.

Then we build the result by doing a DFS on the tree constructed by the BFS.

The difference between normal and double BFS is that the search changes from O(k^d) to O(k^(d/2) + k^(d/2)). Same complexity class, right? Yeah, tell it to the Facebook guys that have to search in graphs with hundreds of thousands of nodes.

C++ code:

https://discuss.leetcode.com/topic/8343/use-defaultdict-for-traceback-and-easy-writing-20-lines-python-code

Use defaultdict for traceback and easy writing, 20 lines python code

Every level we use the defaultdict to get rid of the duplicates

https://discuss.leetcode.com/topic/2857/share-two-similar-java-solution-that-accpted-by-oj

Share two similar Java solution that Accpted by OJ.

The solution contains two steps 1 Use BFS to construct a graph. 2. Use DFS to construct the paths from end to start.Both solutions got AC within 1s.

The first step BFS is quite important. I summarized three tricks

1. Using a MAP to store the min ladder of each word, or use a SET to store the words visited in current ladder, when the current ladder was completed, delete the visited words from unvisited. That’s why I have two similar solutions.
2. Use Character iteration to find all possible paths. Do not compare one word to all the other words and check if they only differ by one character.
3. One word is allowed to be inserted into the queue only ONCE. See my comments.

Another solution using two sets. This is similar to the answer in the most viewed thread. While I found my solution more readable and efficient.

https://discuss.leetcode.com/topic/2857/share-two-similar-java-solution-that-accpted-by-oj

Share two similar Java solution that Accpted by OJ.

The solution contains two steps 1 Use BFS to construct a graph. 2. Use DFS to construct the paths from end to start.Both solutions got AC within 1s.

The first step BFS is quite important. I summarized three tricks

Using a MAP to store the min ladder of each word, or use a SET to store the words visited in current ladder, when the current ladder was completed, delete the visited words from unvisited. That’s why I have two similar solutions.
Use Character iteration to find all possible paths. Do not compare one word to all the other words and check if they only differ by one character.
One word is allowed to be inserted into the queue only ONCE. See my comments.
public class Solution {
Map<String,List> map;
List<List> results;
public List<List> findLadders(String start, String end, Set dict) {
results= new ArrayList<List>();
if (dict.size() == 0)
return results;

``````    int min=Integer.MAX_VALUE;

Queue<String> queue= new ArrayDeque<String>();

map = new HashMap<String,List<String>>();

for (String string:dict)

//BFS: Dijisktra search
while (!queue.isEmpty()) {

String word = queue.poll();

int step = ladder.get(word)+1;//'step' indicates how many steps are needed to travel to one word.

if (step>min) break;

for (int i = 0; i < word.length(); i++){
StringBuilder builder = new StringBuilder(word);
for (char ch='a';  ch <= 'z'; ch++){
builder.setCharAt(i,ch);
String new_word=builder.toString();

if (step>ladder.get(new_word))//Check if it is the shortest path to one word.
continue;
}else;// It is a KEY line. If one word already appeared in one ladder,
// Do not insert the same word inside the queue twice. Otherwise it gets TLE.

else{
map.put(new_word,list);
//It is possible to write three lines in one:
//Which one is better?
}

if (new_word.equals(end))
min=step;

}//End if dict contains new_word
}//End:Iteration from 'a' to 'z'
}//End:Iteration from the first to the last
}//End While

//BackTracking
backTrace(end,start,result);

return results;
}
private void backTrace(String word,String start,List<String> list){
if (word.equals(start)){
list.remove(0);
return;
}
if (map.get(word)!=null)
for (String s:map.get(word))
backTrace(s,start,list);
list.remove(0);
}
``````

}
Another solution using two sets. This is similar to the answer in the most viewed thread. While I found my solution more readable and efficient.

https://discuss.leetcode.com/topic/27504/my-concise-java-solution-based-on-bfs-and-dfs

My concise JAVA solution based on BFS and DFS

Explanation

The basic idea is:

1). Use BFS to find the shortest distance between start and end, tracing the distance of crossing nodes from start node to end node, and store node’s next level neighbors to HashMap;

2). Use DFS to output paths with the same distance as the shortest distance from distance HashMap: compare if the distance of the next level node equals the distance of the current node + 1.

Solution 1:

672ms, 40.34%, June.24th, 2016

https://leetcode.com/discuss/24191/defaultdict-for-traceback-and-easy-writing-lines-python-code