leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0126.cpp (1836B)

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