C++, BFS, hashed look-ups -> O(size(bank)) running time


  • 0
    K
    // Convert the bank into a graph and run BFS to get a shortest path
    int minMutation(string start, string end, vector<string>& bank) {
        // check for the trivial case and return a wrong answer to match the OJ
        if( start == end ) return -1;
    
        // assign integer labels to the strings in the bank, the strings in map are hased by default
        map<string,int> hash;
        hash[start] = 0; // start is not in the bank -> add it separately
        int index = 1;
        for_each( bank.begin(), bank.end(), [&hash,&index](string &s) { hash[s] = index++; } );
    
        // initialize the graph with verticies (labeled strings) and empty lists
        map<int,list<int>> graph;
        for(int i=0; i<index; i++)
            graph.insert( make_pair(i,list<int>()) );
    
        // associate vertex with all other vertices that are different by exactly one symbol
        //  although we use a nested loop, the string's length is fixed -> only a constant factor in the running time
        map<char,array<char,3>> replacement = {{'A',{'C','T','G'}},{'C',{'A','T','G'}},{'T',{'C','A','G'}},{'G',{'C','T','A'}}};
        for_each( graph.begin(),
                  graph.end(),
                  [&hash,&bank,&replacement,&start] (pair<const int,list<int>> &v) {
                        string gene = ( v.first == 0 ? start : bank[v.first-1] );
                        // try replacing every single symbol in the string
                        for(int pos=0; pos<gene.length(); pos++)
                            // run over all the replacement variants
                            for(auto symbol : replacement[ gene[pos] ]){
                                string newGene = gene;
                                // replace
                                newGene[pos] = symbol;
                                // look for the match in the bank
                                auto match = hash.find(newGene);
                                if( match != hash.end() )
                                    v.second.push_back( match->second );
                           }
    
                  }
        );
    
        // canonical BFS, nothing to comment here:
        int retval = -1;
        map<int,int> path;
        queue<int> fifo;
        fifo.push(0);
        set<int> explored;
        while( !fifo.empty() && retval<0 ){
            int node = fifo.front();
            fifo.pop();
            explored.insert(node);
            for(auto n : graph[node])
                if( explored.find(n) == explored.end() ){
                    explored.insert(n);
                    fifo.push(n);
                    path[n] = path[node] + 1;
                    if( bank[n-1] == end ){
                        retval = path[node] + 1;
                        break;
                    }
                }
        }
        return retval;
    }

Log in to reply
 

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