Solution by bfs and dfs output path.


  • 0
    L
    1. Keep two dictionary to maintain the information of a vertex:

    dist: the distance to start

    prev: a list of previous vertices on the shortest path.

    1. Use dfs to traverse prev, output the path from start to end.

      class Solution {
      public:
      void dfsOutputPath(string end, unordered_map<string, vector<string> >& prev, vector<string> sofar, vector<vector<string> >& res) {
      vector<string> newSofar;
      newSofar.push_back(end);
      newSofar.insert(newSofar.end(), sofar.begin(), sofar.end());

           if (prev.count(end) == 0 || prev[end].empty()) {
               res.push_back(newSofar);
           } else {
               vector<string>& prevs = prev[end];
               for (int i = 0; i < prevs.size(); ++i) {
                   dfsOutputPath(prevs[i], prev, newSofar, res);
               }
           }
       }
       
       vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
           if (start == end) return vector<vector<string> >(1, vector<string>(1, start));
           
           vector<vector<string> > res;
           
           // bfs
           queue<string> q;
           unordered_map<string, int> dist;
           unordered_map<string, vector<string> > prev;
           
           dist[start] = 0;
           q.push(start);
           
           while (!q.empty()) {
               string u = q.front();
               q.pop();
               
               if (dist.count(end) > 0 && dist[u] >= dist[end]) break;
               
               // for all (u, v) in E
               for (int i = 0; i < u.size(); ++i) {
                   char c = u[i];
                   for (int j = 0; j < 26; ++j) {
                       char swapped = 'a' + j;
                       if (swapped != c) {
                           string v(u);
                           v[i] = swapped;
                           
                           // in dict
                           if (dict.count(v) > 0 || v == end) {
                               // v is not visited
                               if (dist.count(v) == 0) {
                                   dist[v] = dist[u] + 1;
                                   prev[v] = vector<string>(1, u);
                                   q.push(v);
                               } else {
                                   // v is on another shortest path
                                   if (dist[v] == dist[u] + 1) {
                                       prev[v].push_back(u);
                                   }
                               }
                           }
                       }
                   }
               }
           }
           
           if (dist.count(end) > 0) dfsOutputPath(end, prev, vector<string>(), res);
           
           return res;
       }
      

      };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.