1
// BFS gives TLE if we store path while traversing because whenever we find a
2
// better visit time for a word, we have to clear/make a new path vector
3
// everytime. The idea is to first use BFS to search from beginWord to endWord
4
// and generate the word-to-children mapping at the same time. Then, use DFS
5
// (backtracking) to generate the transformation sequences according to the
6
// mapping. The reverse DFS allows us to only make the shortest paths, never
7
// having to clear a whole sequence when we encounter better result in BFS No
8
// string operations are done, by dealing with indices instead.
9

10
class Solution {
11
 public:
12
  bool able(string s, string t) {
13
    int c = 0;
14
    for (int i = 0; i < s.length(); i++) c += (s[i] != t[i]);
15
    return c == 1;
16
  }
17
  void bfs(vector<vector<int>> &g, vector<int> parent[], int n, int start, int end) {
18
    vector<int> dist(n, 1005);
19
    queue<int> q;
20
    q.push(start);
21
    parent[start] = {-1};
22
    dist[start] = 0;
23
    while (!q.empty()) {
24
      int x = q.front();
25
      q.pop();
26
      for (int u : g[x]) {
27
        if (dist[u] > dist[x] + 1) {
28
          dist[u] = dist[x] + 1;
29
          q.push(u);
30
          parent[u].clear();
31
          parent[u].push_back(x);
32
        } else if (dist[u] == dist[x] + 1)
33
          parent[u].push_back(x);
34
      }
35
    }
36
  }
37
  void shortestPaths(vector<vector<int>> &Paths, vector<int> &path, vector<int> parent[],
38
                     int node) {
39
    if (node == -1) {
40
      // as parent of start was -1, we've completed the backtrack
41
      Paths.push_back(path);
42
      return;
43
    }
44
    for (auto u : parent[node]) {
45
      path.push_back(u);
46
      shortestPaths(Paths, path, parent, u);
47
      path.pop_back();
48
    }
49
  }
50
  vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList) {
51
    // start and end are indices of beginWord and endWord
52
    int n = wordList.size(), start = -1, end = -1;
53
    vector<vector<string>> ANS;
54
    for (int i = 0; i < n; i++) {
55
      if (wordList[i] == beginWord) start = i;
56
      if (wordList[i] == endWord) end = i;
57
    }
58

59
    // if endWord doesn't exist, return empty list
60
    if (end == -1) return ANS;
61

62
    // if beginWord doesn't exist, add it in start of WordList
63
    if (start == -1) {
64
      wordList.emplace(wordList.begin(), beginWord);
65
      start = 0;
66
      end++;
67
      n++;
68
    }
69
    // for each word, we're making adjency list of neighbour words (words that
70
    // can be made with one letter change) Paths will store all the shortest
71
    // paths (formed later by backtracking)
72
    vector<vector<int>> g(n, vector<int>()), Paths;
73

74
    // storing possible parents for each word (to backtrack later), path is the
75
    // current sequence (while backtracking)
76
    vector<int> parent[n], path;
77

78
    // creating adjency list for each pair of words in the wordList (including
79
    // beginword)
80
    for (int i = 0; i < n - 1; i++)
81
      for (int j = i + 1; j < n; j++)
82
        if (able(wordList[i], wordList[j])) {
83
          g[i].push_back(j);
84
          g[j].push_back(i);
85
        }
86

87
    bfs(g, parent, n, start, end);
88

89
    // backtracking to make shortestpaths
90
    shortestPaths(Paths, path, parent, end);
91
    for (auto u : Paths) {
92
      vector<string> now;
93
      for (int i = 0; i < u.size() - 1; i++) now.push_back(wordList[u[i]]);
94
      reverse(now.begin(), now.end());
95
      now.push_back(wordList[end]);
96
      ANS.push_back(now);
97
    }
98
    return ANS;
99
  }
100
};