0126.cpp (1836B)
1 class Solution { 2 unordered_map<string, vector<string>> adj; 3 vector<vector<string>> res; 4 vector<string> state; 5 6 void dfs(const string &crnt, int lvl) { 7 if (lvl == 0) { 8 res.push_back(state); 9 return; 10 } 11 12 for (const auto &word : adj[crnt]) { 13 state[lvl - 1] = word; 14 dfs(word, lvl - 1); 15 } 16 } 17 18 public: 19 vector<vector<string>> findLadders(const string &beginWord, const string &endWord, 20 vector<string> &wordList) { 21 unordered_set<string> set(begin(wordList), end(wordList)); 22 unordered_set<string> seen; 23 queue<string> q; 24 25 q.push(beginWord); 26 for (int lvl = 1; !q.empty(); lvl++) { 27 for (int k = size(q); k > 0; k--) { 28 const auto root = q.front(); 29 q.pop(); 30 31 cout << root << endl; 32 if (root == endWord) { 33 state = vector<string>(lvl); 34 state[lvl - 1] = endWord; 35 dfs(root, lvl - 1); 36 return res; 37 } 38 39 auto crnt = root; 40 for (int i = 0; i < size(crnt); i++) { 41 const char og = crnt[i]; 42 for (char c = 'a'; c <= 'z'; c++) { 43 crnt[i] = c; 44 if (!set.count(crnt)) continue; 45 if (!seen.count(crnt)) { 46 seen.emplace(crnt); 47 q.push(crnt); 48 } 49 adj[crnt].push_back(root); 50 } 51 crnt[i] = og; 52 } 53 } 54 55 for (const auto &word : seen) 56 set.erase(word); 57 } 58 59 return {}; 60 } 61 };