<p>A gene string can be represented by an 8-character long string, with choices from <code>&#39;A&#39;</code>, <code>&#39;C&#39;</code>, <code>&#39;G&#39;</code>, and <code>&#39;T&#39;</code>.</p>

<p>Suppose we need to investigate a mutation from a gene string <code>startGene</code> to a gene string <code>endGene</code> where one mutation is defined as one single character changed in the gene string.</p>

<ul>
	<li>For example, <code>&quot;AACCGGTT&quot; --&gt; &quot;AACCGGTA&quot;</code> is one mutation.</li>
</ul>

<p>There is also a gene bank <code>bank</code> that records all the valid gene mutations. A gene must be in <code>bank</code> to make it a valid gene string.</p>

<p>Given the two gene strings <code>startGene</code> and <code>endGene</code> and the gene bank <code>bank</code>, return <em>the minimum number of mutations needed to mutate from </em><code>startGene</code><em> to </em><code>endGene</code>. If there is no such a mutation, return <code>-1</code>.</p>

<p>Note that the starting point is assumed to be valid, so it might not be included in the bank.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> startGene = &quot;AACCGGTT&quot;, endGene = &quot;AACCGGTA&quot;, bank = [&quot;AACCGGTA&quot;]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> startGene = &quot;AACCGGTT&quot;, endGene = &quot;AAACGGTA&quot;, bank = [&quot;AACCGGTA&quot;,&quot;AACCGCTA&quot;,&quot;AAACGGTA&quot;]
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= bank.length &lt;= 10</code></li>
	<li><code>startGene.length == endGene.length == bank[i].length == 8</code></li>
	<li><code>startGene</code>, <code>endGene</code>, and <code>bank[i]</code> consist of only the characters <code>[&#39;A&#39;, &#39;C&#39;, &#39;G&#39;, &#39;T&#39;]</code>.</li>
</ul>

// class Solution {
// public:
//     int minMutation(string startGene, string endGene, vector<string>& bank) {
        
//         set<string>set_banks(bank.begin(), bank.end());
//         int ptr1 = 0, ptr2=0;
//         int  ans =0;
//         // map< char, pair<char, int> >to_replace;
//         set<int>st;
//         while(ptr1 < startGene.length())
//         {
//             if( startGene[ptr1] != endGene[ptr2] )
//             {
//                 // to_replace[startGene[ptr1]] = {endGene[ptr2], ptr1};
//                 st.insert(ptr1);
//             }

            
//             ptr1++;
//             ptr2++;
//         }

//         while(startGene!=endGene)
//         {
//             for(auto it: st)
//             {
//                 string dup_start = startGene;
//                 dup_start[it] = endGene[it];
//                 cout<<startGene[it]<<" ";
//                 if(set_banks.find(dup_start) != set_banks.end() )
//                 {
//                     st.erase(it);
//                     startGene[it]=endGene[it];
//                     ans++;
//                 }

//             }
            
//             if(ans==0) return -1;
//         }

//         return ans;

//     }
// };







class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        int size = bank.size(); // extract size
        
        unordered_set<string> dictionary; // make dictionary set 
        for(int i = 0; i < size; i++) // insert every word of bank into the set
        {
            dictionary.insert(bank[i]);
        }
        
        // if end word is not present into the dictionary,
        // will return false from here
        if(dictionary.find(end) == dictionary.end())
        {
            return -1;
        }
        
        // choices that are availble to us
        vector<char> available = {'A', 'C', 'G', 'T'};
        
        // make vis set, to find out whether for a particular word, 
        // either we previously encountered or not
        unordered_set<string> vis;
        
        int ans = 0; // declare ans variable 
        
        queue<string> q; // define queue to start bfs
        q.push(start); // push starting word into the queue
        vis.insert(start); // insert into vis
        
        // starting bfs
        while(!q.empty())
        {
            int n = q.size(); // extract size of queue
            while(n--)
            {
                string curr = q.front(); // curr word 
                q.pop(); // pop from queue
                
                if(curr == end) // if curr word equals to end, return ans from here
                {
                    return ans;
                }
                
                // now for every index of curr word
                for(int i = 0; i < 8; i++)
                {
                    char orig = curr[i]; 
                    
                    // we will try to replace every available choice
                    for(int j = 0; j < 4; j++) 
                    {   
                        curr[i] = available[j]; // replace character
                        
                        // if it is present into the dictionary
                        if(dictionary.find(curr) != dictionary.end())
                        {
                            // also we haven't seen it previously
                            if(vis.find(curr) == vis.end())
                            {
                                q.push(curr); // then push into queue
                                vis.insert(curr); // and also put into vis
                            }
                        }
                    }
                    // now replace with again original character,
                    // for further check
                    curr[i] = orig;
                }
            }
            ans++; // increment answer
        }
        
        return -1; // still we will not able to find end word, return -1
    }
};
8100