C++ Simple 3ms solution with comments

  • 0
    class Solution {
        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);
            while (!q.empty()){
                pair<string, int> p = q.front();
                //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])){
                    //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);
            //if queue is emptied out then no mutations will work
            return -1;
        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]){
                //break early to avoid comparing entire string if more than 2 chars is different
                if (b)
                    return false;
                b = true;
            return b;

Log in to reply

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