126. Word Ladder II

  • 13.7%

https://leetcode.com/problems/word-ladder-ii/#/description

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.
1
2
3
4
5
6
7
8
9
10
11
For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]

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.


https://discuss.leetcode.com/topic/16826/88ms-accepted-c-solution-with-two-end-bfs-68ms-for-word-ladder-and-88ms-for-word-ladder-ii

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
int ladderLength(std::string beginWord, std::string endWord, std::unordered_set<std::string> &dict) {
if (beginWord == endWord)
return 1;
std::unordered_set<std::string> words1, words2;
words1.insert(beginWord);
words2.insert(endWord);
dict.erase(beginWord);
dict.erase(endWord);
return ladderLengthHelper(words1, words2, dict, 1);
}

private:
int ladderLengthHelper(std::unordered_set<std::string> &words1, std::unordered_set<std::string> &words2, std::unordered_set<std::string> &dict, int level) {
if (words1.empty())
return 0;
if (words1.size() > words2.size())
return ladderLengthHelper(words2, words1, dict, level);
std::unordered_set<std::string> words3;
for (auto it = words1.begin(); it != words1.end(); ++it) {
std::string word = *it;
for (auto ch = word.begin(); ch != word.end(); ++ch) {
char tmp = *ch;
for (*ch = 'a'; *ch <= 'z'; ++(*ch))
if (*ch != tmp)
if (words2.find(word) != words2.end())
return level + 1;
else if (dict.find(word) != dict.end()) {
dict.erase(word);
words3.insert(word);
}
*ch = tmp;
}
}
return ladderLengthHelper(words2, words3, dict, level + 1);
}
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public:
std::vector<std::vector<std::string> > findLadders(std::string beginWord, std::string endWord, std::unordered_set<std::string> &dict) {
std::vector<std::vector<std::string> > paths;
std::vector<std::string> path(1, beginWord);
if (beginWord == endWord) {
paths.push_back(path);
return paths;
}
std::unordered_set<std::string> words1, words2;
words1.insert(beginWord);
words2.insert(endWord);
std::unordered_map<std::string, std::vector<std::string> > nexts;
bool words1IsBegin = false;
if (findLaddersHelper(words1, words2, dict, nexts, words1IsBegin))
getPath(beginWord, endWord, nexts, path, paths);
return paths;
}
private:
bool findLaddersHelper(
std::unordered_set<std::string> &words1,
std::unordered_set<std::string> &words2,
std::unordered_set<std::string> &dict,
std::unordered_map<std::string, std::vector<std::string> > &nexts,
bool &words1IsBegin) {
words1IsBegin = !words1IsBegin;
if (words1.empty())
return false;
if (words1.size() > words2.size())
return findLaddersHelper(words2, words1, dict, nexts, words1IsBegin);
for (auto it = words1.begin(); it != words1.end(); ++it)
dict.erase(*it);
for (auto it = words2.begin(); it != words2.end(); ++it)
dict.erase(*it);
std::unordered_set<std::string> words3;
bool reach = false;
for (auto it = words1.begin(); it != words1.end(); ++it) {
std::string word = *it;
for (auto ch = word.begin(); ch != word.end(); ++ch) {
char tmp = *ch;
for (*ch = 'a'; *ch <= 'z'; ++(*ch))
if (*ch != tmp)
if (words2.find(word) != words2.end()) {
reach = true;
words1IsBegin ? nexts[*it].push_back(word) : nexts[word].push_back(*it);
}
else if (!reach && dict.find(word) != dict.end()) {
words3.insert(word);
words1IsBegin ? nexts[*it].push_back(word) : nexts[word].push_back(*it);
}
*ch = tmp;
}
}
return reach || findLaddersHelper(words2, words3, dict, nexts, words1IsBegin);
}
void getPath(
std::string beginWord,
std::string &endWord,
std::unordered_map<std::string, std::vector<std::string> > &nexts,
std::vector<std::string> &path,
std::vector<std::vector<std::string> > &paths) {
if (beginWord == endWord)
paths.push_back(path);
else
for (auto it = nexts[beginWord].begin(); it != nexts[beginWord].end(); ++it) {
path.push_back(*it);
getPath(*it, endWord, nexts, path, paths);
path.pop_back();
}
}
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution 
{
public:
vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &dict) {
vector<vector<string> > paths;
vector<string> path(1, beginWord);
if (beginWord == endWord) //corner case;
{
paths.push_back(path);
return paths;
}
unordered_set<string> forward, backward;
forward.insert(beginWord);
backward.insert(endWord);
unordered_map<string, vector<string> > tree;
bool reversed = false; //make sure the tree generating direction is consistent, since we have to start from the smaller set to accelerate;
if (buildTree(forward, backward, dict, tree, reversed))
getPath(beginWord, endWord, tree, path, paths);
return paths;
}
private:
bool buildTree(unordered_set<string> &forward, unordered_set<string> &backward, unordered_set<string> &dict, unordered_map<string, vector<string> > &tree, bool reversed)
{
if (forward.empty()) return false;
if (forward.size() > backward.size())
return buildTree(backward, forward, dict, tree, !reversed);
for (auto &word: forward) dict.erase(word);
for (auto &word: backward) dict.erase(word);
unordered_set<string> nextLevel;
bool done = false; //in case of invalid further searching;
for (auto &it: forward) //traverse each word in the forward -> the current level of the tree;
{
string word = it;
for (auto &c: word)
{
char c0 = c; //store the original;
for (c = 'a'; c <= 'z'; ++c) //try each case;
{
if (c != c0) //avoid futile checking;
{
if (backward.count(word)) //using count is an accelerating method;
{
done = true;
!reversed ? tree[it].push_back(word) : tree[word].push_back(it); //keep the tree generation direction consistent;
}
else if (!done && dict.count(word))
{
nextLevel.insert(word);
!reversed ? tree[it].push_back(word) : tree[word].push_back(it);
}
}
}
c = c0; //restore the word;
}
}
return done || buildTree(nextLevel, backward, dict, tree, reversed);
}

void getPath(string &beginWord, string &endWord, unordered_map<string, vector<string> > &tree, vector<string> &path, vector<vector<string> > &paths) //using reference can accelerate;
{
if (beginWord == endWord) paths.push_back(path); //till the end;
else
{
for (auto &it: tree[beginWord])
{
path.push_back(it);
getPath(it, endWord, tree, path, paths); //DFS retrieving the path;
path.pop_back();
}
}
}
};

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution(object):

# Solution using double BFS

def findLadders(self, begin, end, words_list):

def construct_paths(source, dest, tree):
if source == dest:
return [[source]]
return [[source] + path for succ in tree[source]
for path in construct_paths(succ, dest, tree)]

def add_path(tree, word, neigh, is_forw):
if is_forw: tree[word] += neigh,
else: tree[neigh] += word,

def bfs_level(this_lev, oth_lev, tree, is_forw, words_set):
if not this_lev: return False
if len(this_lev) > len(oth_lev):
return bfs_level(oth_lev, this_lev, tree, not is_forw, words_set)
for word in (this_lev | oth_lev):
words_set.discard(word)
next_lev, done = set(), False
while this_lev:
word = this_lev.pop()
for c in string.ascii_lowercase:
for index in range(len(word)):
neigh = word[:index] + c + word[index+1:]
if neigh in oth_lev:
done = True
add_path(tree, word, neigh, is_forw)
if not done and neigh in words_set:
next_lev.add(neigh)
add_path(tree, word, neigh, is_forw)
return done or bfs_level(next_lev, oth_lev, tree, is_forw, words_set)

tree, path, paths = collections.defaultdict(list), [begin], []
is_found = bfs_level(set([begin]), set([end]), tree, True, words_list)
return construct_paths(begin, end, tree)

C++ code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
void add_to_tree(map<string, vector<string>>& tree, 
string word,
string neigh,
bool forward) {
if (forward) tree[word].push_back(neigh);
else tree[neigh].push_back(word);

}

vector<vector<string>> construct_paths(map<string,
vector<string>>& tree,
string start,
string dest) {
if (start == dest) {
vector<string> res = {start};
vector<vector<string>> arr = {res};
return arr;
}
vector<vector<string>> result;

for (auto succ: tree[start]) {
for (auto path: construct_paths(tree, succ, dest)) {
path.insert(path.begin(), start);
result.push_back(path);
}
}
return result;
}

bool bfs_levels(unordered_set<string>& now,
unordered_set<string>& oth,
bool& forward,
map<string, vector<string>>& tree,
unordered_set<string>& words_list,
vector<char>& alphabet) {

if (not now.size()) return false;
if (now.size() > oth.size()){
forward = not forward;
return bfs_levels(oth, now, forward, tree, words_list, alphabet);
}
for (auto word: now) words_list.erase(word);
for (auto word: oth) words_list.erase(word);

bool done = false; unordered_set<string> next;

for (string word: now) {
for (int i = 0; i < word.size(); i++) {
for (char c: alphabet) {
auto neigh = word.substr(0, i) + c + word.substr(i+1);
if (oth.count(neigh) > 0) {
done = true;
add_to_tree(tree, word, neigh, forward);
}
else {
if (not done and words_list.count(neigh) > 0) {
next.insert(neigh);
add_to_tree(tree, word, neigh, forward);
}
}
}
}
}
forward = not forward;
return done or bfs_levels(oth, next, forward, tree, words_list, alphabet);
}


class Solution {
public:
vector<vector<string>> findLadders(string beginWord,
string endWord,
unordered_set<string> &wordList) {

vector<char> alphabet(26);
std::iota(alphabet.begin(), alphabet.end(), 'a');
unordered_set<string> now = {beginWord}, oth = {endWord};
map<string, vector<string>> tree; bool forward = true;
auto is_found = bfs_levels(now, oth, forward, tree, wordList, alphabet);
return construct_paths(tree, beginWord, endWord);

}
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return a list of lists of string
def findLadders(self, start, end, dic):
dic.add(end)
level = {start}
parents = collections.defaultdict(set)
while level and end not in parents:
next_level = collections.defaultdict(set)
for node in level:
for char in string.ascii_lowercase:
for i in range(len(start)):
n = node[:i]+char+node[i+1:]
if n in dic and n not in parents:
next_level[n].add(node)
level = next_level
parents.update(next_level)
res = [[end]]
while res and res[0][0] != start:
res = [[p]+r for r in res for p in parents[r[0]]]
return res

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
public class Solution {
Map<String,List<String>> map;
List<List<String>> results;
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
results= new ArrayList<List<String>>();
if (dict.size() == 0)
return results;

int min=Integer.MAX_VALUE;

Queue<String> queue= new ArrayDeque<String>();
queue.add(start);

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

Map<String,Integer> ladder = new HashMap<String,Integer>();
for (String string:dict)
ladder.put(string, Integer.MAX_VALUE);
ladder.put(start, 0);

dict.add(end);
//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 (ladder.containsKey(new_word)) {

if (step>ladder.get(new_word))//Check if it is the shortest path to one word.
continue;
else if (step<ladder.get(new_word)){
queue.add(new_word);
ladder.put(new_word, step);
}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.

if (map.containsKey(new_word)) //Build adjacent Graph
map.get(new_word).add(word);
else{
List<String> list= new LinkedList<String>();
list.add(word);
map.put(new_word,list);
//It is possible to write three lines in one:
//map.put(new_word,new LinkedList<String>(Arrays.asList(new String[]{word})));
//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
LinkedList<String> result = new LinkedList<String>();
backTrace(end,start,result);

return results;
}
private void backTrace(String word,String start,List<String> list){
if (word.equals(start)){
list.add(0,start);
results.add(new ArrayList<String>(list));
list.remove(0);
return;
}
list.add(0,word);
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
public class Solution {
List<List<String>> results;
List<String> list;
Map<String,List<String>> map;
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
results= new ArrayList<List<String>>();
if (dict.size() == 0)
return results;

int curr=1,next=0;
boolean found=false;
list = new LinkedList<String>();
map = new HashMap<String,List<String>>();

Queue<String> queue= new ArrayDeque<String>();
Set<String> unvisited = new HashSet<String>(dict);
Set<String> visited = new HashSet<String>();

queue.add(start);
unvisited.add(end);
unvisited.remove(start);
//BFS
while (!queue.isEmpty()) {

String word = queue.poll();
curr--;
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 (unvisited.contains(new_word)){
//Handle queue
if (visited.add(new_word)){//Key statement,Avoid Duplicate queue insertion
next++;
queue.add(new_word);
}

if (map.containsKey(new_word))//Build Adjacent Graph
map.get(new_word).add(word);
else{
List<String> l= new LinkedList<String>();
l.add(word);
map.put(new_word, l);
}

if (new_word.equals(end)&&!found) found=true;

}

}//End:Iteration from 'a' to 'z'
}//End:Iteration from the first to the last
if (curr==0){
if (found) break;
curr=next;
next=0;
unvisited.removeAll(visited);
visited.clear();
}
}//End While

backTrace(end,start);

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

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>();
    queue.add(start);

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

    Map<String,Integer> ladder = new HashMap<String,Integer>();
    for (String string:dict)
        ladder.put(string, Integer.MAX_VALUE);
    ladder.put(start, 0);

    dict.add(end);
    //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 (ladder.containsKey(new_word)) {

                    if (step>ladder.get(new_word))//Check if it is the shortest path to one word.
                        continue;
                    else if (step<ladder.get(new_word)){
                        queue.add(new_word);
                        ladder.put(new_word, step);
                    }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.

                    if (map.containsKey(new_word)) //Build adjacent Graph
                        map.get(new_word).add(word);
                    else{
                        List<String> list= new LinkedList<String>();
                        list.add(word);
                        map.put(new_word,list);
                        //It is possible to write three lines in one:
                        //map.put(new_word,new LinkedList<String>(Arrays.asList(new String[]{word})));
                        //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
    LinkedList<String> result = new LinkedList<String>();
    backTrace(end,start,result);

    return results;        
}
private void backTrace(String word,String start,List<String> list){
    if (word.equals(start)){
        list.add(0,start);
        results.add(new ArrayList<String>(list));
        list.remove(0);
        return;
    }
    list.add(0,word);
    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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
public class Solution {
List<List<String>> results;
List<String> list;
Map<String,List<String>> map;
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
results= new ArrayList<List<String>>();
if (dict.size() == 0)
return results;

int curr=1,next=0;
boolean found=false;
list = new LinkedList<String>();
map = new HashMap<String,List<String>>();

Queue<String> queue= new ArrayDeque<String>();
Set<String> unvisited = new HashSet<String>(dict);
Set<String> visited = new HashSet<String>();

queue.add(start);
unvisited.add(end);
unvisited.remove(start);
//BFS
while (!queue.isEmpty()) {

String word = queue.poll();
curr--;
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 (unvisited.contains(new_word)){
//Handle queue
if (visited.add(new_word)){//Key statement,Avoid Duplicate queue insertion
next++;
queue.add(new_word);
}

if (map.containsKey(new_word))//Build Adjacent Graph
map.get(new_word).add(word);
else{
List<String> l= new LinkedList<String>();
l.add(word);
map.put(new_word, l);
}

if (new_word.equals(end)&&!found) found=true;

}

}//End:Iteration from 'a' to 'z'
}//End:Iteration from the first to the last
if (curr==0){
if (found) break;
curr=next;
next=0;
unvisited.removeAll(visited);
visited.clear();
}
}//End While

backTrace(end,start);

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

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
public List<List<String>> findLadders(String start, String end, List<String> wordList) {
HashSet<String> dict = new HashSet<String>(wordList);
List<List<String>> res = new ArrayList<List<String>>();
HashMap<String, ArrayList<String>> nodeNeighbors = new HashMap<String, ArrayList<String>>();// Neighbors for every node
HashMap<String, Integer> distance = new HashMap<String, Integer>();// Distance of every node from the start node
ArrayList<String> solution = new ArrayList<String>();

dict.add(start);
bfs(start, end, dict, nodeNeighbors, distance);
dfs(start, end, dict, nodeNeighbors, distance, solution, res);
return res;
}

// BFS: Trace every node's distance from the start node (level by level).
private void bfs(String start, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance) {
for (String str : dict)
nodeNeighbors.put(str, new ArrayList<String>());

Queue<String> queue = new LinkedList<String>();
queue.offer(start);
distance.put(start, 0);

while (!queue.isEmpty()) {
int count = queue.size();
boolean foundEnd = false;
for (int i = 0; i < count; i++) {
String cur = queue.poll();
int curDistance = distance.get(cur);
ArrayList<String> neighbors = getNeighbors(cur, dict);

for (String neighbor : neighbors) {
nodeNeighbors.get(cur).add(neighbor);
if (!distance.containsKey(neighbor)) {// Check if visited
distance.put(neighbor, curDistance + 1);
if (end.equals(neighbor))// Found the shortest path
foundEnd = true;
else
queue.offer(neighbor);
}
}
}

if (foundEnd)
break;
}
}

// Find all next level nodes.
private ArrayList<String> getNeighbors(String node, Set<String> dict) {
ArrayList<String> res = new ArrayList<String>();
char chs[] = node.toCharArray();

for (char ch ='a'; ch <= 'z'; ch++) {
for (int i = 0; i < chs.length; i++) {
if (chs[i] == ch) continue;
char old_ch = chs[i];
chs[i] = ch;
if (dict.contains(String.valueOf(chs))) {
res.add(String.valueOf(chs));
}
chs[i] = old_ch;
}

}
return res;
}

// DFS: output all paths with the shortest distance.
private void dfs(String cur, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance, ArrayList<String> solution, List<List<String>> res) {
solution.add(cur);
if (end.equals(cur)) {
res.add(new ArrayList<String>(solution));
} else {
for (String next : nodeNeighbors.get(cur)) {
if (distance.get(next) == distance.get(cur) + 1) {
dfs(next, end, dict, nodeNeighbors, distance, solution, res);
}
}
}
solution.remove(solution.size() - 1);
}

Solution 1:

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
def findLadders(self, beginWord, endWord, wordlist):
"""
:type beginWord: str
:type endWord: str
:type wordlist: Set[str]
:rtype: List[List[int]]
"""
wordlist.add(endWord)
level = {beginWord}
parents = collections.defaultdict(set)
while level and endWord not in parents:
next_level = collections.defaultdict(set)
for node in level:
for char in string.ascii_lowercase:
for i in range(len(beginWord)):
n = node[:i]+char+node[i+1:]
if n in wordlist and n not in parents:
next_level[n].add(node)
level = next_level
parents.update(next_level)
res = [[endWord]]
while res and res[0][0] != beginWord:
res = [[p]+r for r in res for p in parents[r[0]]]
return res
谢谢你,可爱的朋友。