C++ Simple 3ms solution with comments


  • 0
    S
    class Solution {
    public:
        int minMutation(string start, string end, vector<string>& bank) {       
            if (start == end){
                //if start is not a valid gene then return -1        
                if (find(bank.begin(), bank.end(), start) == bank.end()){
                    return -1; //Technically this should be 0, but when 
                               //I run the test cases the expected result is 1
                } else {
                    return 1;
                }
            }
            if (bank.empty())
                return -1;
                
            //If the end is not a valid gene then return -1
            if (find(bank.begin(), bank.end(), end) == bank.end())
                return -1;
            
            queue<pair<string, int> > q;
            pair<string, int> pairStart(start, 0);
            q.push(pairStart);
            while (!q.empty()){
                pair<string, int> p = q.front();
                q.pop();
                
                //evaluate current genes
                const string& gene = p.first;
                const int current_level = p.second;
                
                //check bank for genes that are only 1 off from the current gene
                for (int i=0; i<bank.size(); ++i){
                    if (!isMutation(gene, bank[i])){
                        continue;
                    }
                    //if a mutation is found, and it's end then return level 
                    if (bank[i] == end){
                        return current_level + 1;
                    }
                    //if a mutation is found, but not equals to end, insert into 
                    //queue with incremented level for later processing
                    pair<string, int> new_gene(bank[i], current_level+1);
                    q.push(new_gene);
                }
            }
        
            //if queue is emptied out then no mutations will work
            return -1;
        }
    private:
        bool isMutation(const string& s, const string& m){
            if (s.size() != m.size())
                return false;
            bool b = false;
            int i = 0;
            while (i < s.size()){
                if (s[i] == m[i]){
                    ++i;
                    continue;
                }
                //break early to avoid comparing entire string if more than 2 chars is different
                if (b)
                    return false;
                b = true;
                ++i;
            }
            return b;
        }
    };
    

Log in to reply
 

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