Algorithm

LintCode/Word Ladder II

Problem Summary

Given two words (start and end), and a dictionary,(All words have the same length), find all shortest transformation sequence(s) from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

Solution

We can use Breadth First Search(BFS) to find the shortest transformation sequences. In order to save time, we can use the container “unordered_set” in STL to keep a record of visited strings.

In addition, we need to find all shortest sequences, not just any of them, so I think there are two things we need to do.

  1. Instead of stopping the search right after we find the shortest length, we continue the search until next level of the search tree.

  2. We allow there to be same strings in each level of the search tree.
    To implement this, we can use two unordered sets, pre_visited and cur_level_visited. The first contains all strings that have been searched before this level, while the second only contains the strings of this level. Suppose we have a string S in current level, if S is in the dictionary and not in the pre_visited set, then we add it to the end of the queue and insert it into the cur_level_visited set. After each level, we insert all elements in cur_level_visited set to pre_visited set, and clear the cur_level_visited set.

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
84
85
86
87
class Solution {
public:
    /*
     * @param start: a string
     * @param end: a string
     * @param dict: a set of string
     * @return: a list of lists of string
     */
    vector<string> q;
    vector<int> pre;
        
    vector<vector<string> > findLadders(string &start, string &end, unordered_set<string> &dict) {
        vector<vector<string> > res;
        if (start == end)
        {
            vector<string> tmp(2,"");
            tmp[0] = start;
            tmp[1] = end;
            res.push_back(tmp);
            return res;
        }
        dict.insert(end);
        unordered_set<string> vis;
        
        q.push_back(start);
        pre.push_back(-1);
        int head = 0, tail = 1;
        vis.insert(start);
        int n = start.length();
        int level = 1;
        bool found = false;
        while (head<tail && !found)
        {
            ++level;
            int num = tail - head;
            unordered_set<string> this_level;
            while (num--)
            {
                string cur = q[head++];
                
                for (int i = 0; i < n; ++i)
                {
                    string y = cur;
                    for (int j = 'a'; j <= 'z'; ++j)
                    if (j!=cur[i])
                    {
                         y[i] = j;
                        if (y == end)
                        {
                            found = true;
                            vector<string> tmp(level,"");
                            tmp[level-1] = end;
                            int idx = head-1;
                            for (int k = level-2; k >= 0 ; --k)
                            {
                                tmp[k] = q[idx];
                                idx = pre[idx];
                            }
                            res.push_back(tmp);
                        }
                        else
                        if (dict.count(y) && vis.count(y)==0)
                        {
                            this_level.insert(y);
                            q.push_back(y);
                            pre.push_back(head-1);
                            ++tail;
                        }
                    }
                }
            }
            if (!found)
            {
                for (unordered_set<string>::iterator i = this_level.begin(); i != this_level.end(); ++i)
                    vis.insert(*i);
            }
        }
        return res;
    }
};