C++ two end BFS 0ms solution


  • 0
    H

    The idea is to do two-end BFS. Use a vector<string> and an unordered_set<string> to store the valid mutation generated from previous ones. To exclude previously used mutations, use a increment to ensure each mutation can be used only once in each end.

                -----> s1 ... e1 <-----
              /                         \
        start  ------> s2 ... e2 <-----  end
              \                         /
               ------> s3 ... e3 <-----
    
    
    class Solution {
    public:
        int minMutation(string start, string end, vector<string>& bank) {
            unordered_map<string, int> map;
            for (auto x : bank) map[x] = 0;
            if (!map.count(end)) return -1; // only start is assumed to be valid. If end not valid, return -1
            vector<string> v = {start};
            unordered_set<string> s = {end};
            int res = 0;
            int increment = 1;
            while (v.size() && s.size()) {
                for (auto x : v) {
                    if (s.count(x)) return res;
                }
                unordered_set<string> tmp = getMutations(map, v, increment);
                v = vector<string>(s.begin(), s.end());
                s.swap(tmp);
                res++;
                increment *= -1;
            }
            return -1;
        }
        
        unordered_set<string> getMutations(unordered_map<string, int>& bank, vector<string>& v, int increment) {
            unordered_set<string> res;
            vector<char> c = {'A', 'C', 'G', 'T'};
            for (auto x : v) {
                for (int i = 0; i < x.size(); i++) {
                    for (int j = 0; j < c.size(); j++) {
                        char tmp = x[i];
                        x[i] = c[j];
                        if (bank.count(x) && abs(bank[x] + increment) < 2) {
                            res.insert(x);
                            bank[x] += increment;
                        }
                        x[i] = tmp;
                    }
                }
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.