C++ CLRS Dijkstra & DFS


  • 0
    class Solution {
     private:
      void DFS(vector<vector<string>>& res,
               unordered_map<string, vector<string>>& pre, vector<string>& cur,
               string v) {
        cur.push_back(v);
        if (!pre.count(v)) {
          res.push_back(vector<string>(cur.rbegin(), cur.rend()));
        } else
          for (auto& p : pre[v]) DFS(res, pre, cur, p);
    
        cur.pop_back();
      }
    
     public:
      vector<vector<string>> findLadders(string beginWord, string endWord,
                                         unordered_set<string>& wordList) {
        wordList.insert(endWord);
        unordered_map<string, int> score;
        for (auto& w : wordList) score[w] = 0x3f3f3f3f;
        unordered_map<string, vector<string>> pre;
        priority_queue<pair<int, string>, vector<pair<int, string>>,
                       greater<pair<int, string>>>
            heap;
        score[beginWord] = 0;
        heap.push(make_pair(0, beginWord));
        while (heap.size()) {
          string v = heap.top().second;
          if (v == endWord) break;
          heap.pop();
          wordList.erase(v);
    
          for (int i = 0; v[i]; i++) {
            string t = v;
            for (char c = 'a'; c <= 'z'; c++) {
              t[i] = c;
              if (wordList.count(t)) {
                if (score[t] > score[v] + 1) {
                  score[t] = score[v] + 1;
                  pre[t].clear();
                  pre[t].push_back(v);
                  heap.push(make_pair(score[t], t));
                } else if (score[t] == score[v] + 1)
                  pre[t].push_back(v);
              }
            }
          }
        }
        vector<vector<string>> res;
        vector<string> cur;
        if (score[endWord] < 0x3f3f3f3f) DFS(res, pre, cur, endWord);
    
        return res;
      }
    };
    

Log in to reply
 

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