433. Minimal Gene Change

https://leetcode-cn.com/problems/minimum-genetic-mutation/.

Solution ideas

Breadth-first search

1. In order to improve performance, we will use a two-way search method
2. How to search in both directions?
   The same as general breadth, the only difference is that each time you need to judge whether to traverse with head or tail
   The most basic guiding principle is:

• Use a small number of traversals first
• In order to facilitate quick search, we use set to replace queue

The code that does not consider the wide search

class Solution {public:int minMutation(string start, string end, vector& bank) {int count = 0;for(int i = 7,j=0; i >= 0 && j < 8; i--,j++){if(start[i]!=end[i]){start[i]=end[i];bool isvalid = false;if(find(bank.begin(),bank.end(),start)!=bank.end()){count++;isvalid = true;}else return -1;}}return count;}};

BFS code

class Solution {public:int minMutation(string start, string end, vector& bank) {// Build the dictionary of the bank first, which is convenient for quick search. If it is used, it will be deleted to avoid loop traversal.unordered_set bankSet;for (string& b : bank){bankSet.insert(b);}// pre-judgmentif (bankSet.find(end) == bankSet.end()){return -1;}// replaceable four characterschar replaces[4] = {'A', 'C', 'G', 'T'};// Build the initialized two head and tail collectionsunordered_set heads = {start};unordered_set tails = {end};// a temporary variable to hold the current collectionunordered_set temp;// Times record: Accumulate according to each layerint rounds = 0;while (!heads.empty() && !tails.empty()){++rounds;// Take the smallest set as the traversed object, the smallest is always in the headsif (heads.size() > tails.size()){swap(heads, tails);}for (const string& head : heads){string curr = head;// loop through each characterint n = curr.size();for (int i = 0; i < n; ++i){char old = curr[i];// replace the four possibilitiesfor (int j = 0; j < 4; ++j){curr[i] = replaces[j];// cout << rounds << " : " << curr << " " << head << endl;// If found in the tail, return directlyif (tails.find(curr) != tails.end()){return rounds;}else if (bankSet.find(curr) != bankSet.end()){bankSet.erase(curr);temp.insert(curr);}}// essential restore charactercurr[i] = old;}}// Quick swap assignment to headsswap(heads, temp);temp.clear();}// if not found, return -1return -1;}};