leetcode

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 };