0433.cpp (1433B)
1 class Solution { 2 bool mutation(const string &s1, const string &s2) { 3 int cnt = 0; 4 for (int i = 0; i < size(s1); i++) 5 if (s1[i] != s2[i]) cnt++; 6 return cnt == 1; 7 } 8 9 public: 10 int minMutation(string startGene, string endGene, vector<string> &bank) { 11 /* unordered_map<string, vector<string>> um; */ 12 13 /* if (find(bank.begin(), bank.end(), startGene) == bank.end()) */ 14 /* bank.push_back(startGene); */ 15 16 /* for (int i = 0; i < size(bank); i++) { */ 17 /* for (int j = i + 1; j < size(bank); j++) */ 18 /* if (mutation(bank[i], bank[j])) { */ 19 /* um[bank[i]].push_back(bank[j]); */ 20 /* um[bank[j]].push_back(bank[i]); */ 21 /* } */ 22 /* } */ 23 24 int mini = INT_MAX; 25 unordered_set<string> visited; 26 queue<pair<string, int>> st; 27 st.push({startGene, 0}); 28 while (!st.empty()) { 29 string root = st.front().first; 30 int count = st.front().second; 31 st.pop(); 32 visited.insert(root); 33 if (root == endGene) return count; 34 /* for (string &s : um[root]) */ 35 /* if (visited.find(s) == visited.end()) st.push({s, count + 1}); */ 36 for (string &s : bank) 37 if (visited.find(s) == visited.end() && mutation(root, s)) st.push({s, count + 1}); 38 } 39 return -1; 40 } 41 };