leetcode

0 class Solution {

1 bool mutation(const string &s1, const string &s2) {

2 int cnt = 0;

3 for (int i = 0; i < size(s1); i++)

4 if (s1[i] != s2[i]) cnt++;

5 return cnt == 1;

6 }

7

8 public:

9 int minMutation(string startGene, string endGene, vector<string> &bank) {

10 /* unordered_map<string, vector<string>> um; */

11

12 /* if (find(bank.begin(), bank.end(), startGene) == bank.end()) */

13 /* bank.push_back(startGene); */

14

15 /* for (int i = 0; i < size(bank); i++) { */

16 /* for (int j = i + 1; j < size(bank); j++) */

17 /* if (mutation(bank[i], bank[j])) { */

18 /* um[bank[i]].push_back(bank[j]); */

19 /* um[bank[j]].push_back(bank[i]); */

20 /* } */

21 /* } */

22

23 int mini = INT_MAX;

24 unordered_set<string> visited;

25 queue<pair<string, int>> st;

26 st.push({startGene, 0});

27 while (!st.empty()) {

28 string root = st.front().first;

29 int count = st.front().second;

30 st.pop();

31 visited.insert(root);

32 if (root == endGene) return count;

33 /* for (string &s : um[root]) */

34 /* if (visited.find(s) == visited.end()) st.push({s, count + 1}); */

35 for (string &s : bank)

36 if (visited.find(s) == visited.end() && mutation(root, s)) st.push({s, count + 1});

37 }

38 return -1;

39 }

40 };