<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:
    
    unordered_map<char, vector<char>> mutations = { {{'A'}, {'C','G','T'}}, 
                                                   {{'C'}, {'A','G','T'}},
                                                   {{'G'}, {'A','C','T'}},
                                                   {{'T'},  {'A','C','G'}}
                                                  };
    unordered_set<string> bankSet;
    
    int sizeOfGene = 8;
    
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        
        // just define these once
  //      mutations['A'] = {'C','G','T'};
  //      mutations['C'] = {'A','G','T'};
  //      mutations['G'] = {'A','C','T'};
  //      mutations['T'] = {'A','C','G'};
        
        // initialize bank set
        for (string gene : bank)
        {
            bankSet.insert(gene);
        }
        
        if (bankSet.find(endGene) == bankSet.end())
        {
            // endGene is not valid, cannot be found
            return -1;
        }
        
        set<string> seen;
        
        queue<pair<string, int>> queue;
        queue.push({startGene,0});
        seen.insert(startGene);
        
        while (!queue.empty())
        {
            auto [gene, steps] = queue.front();
            queue.pop();
            
            if (gene == endGene)
                return steps;
            
            vector<string> possibleMutations = generatePossibleMutations(gene);
            
            for (string mutation : possibleMutations)
            {
                if (seen.find(mutation) == seen.end())      // haven't seen this mutation before
                {
                    seen.insert(mutation);
                    queue.push({mutation, steps+1});
                }
            }
        }
        return -1;
    }
    
    
    vector<string> generatePossibleMutations(string gene)
    {
        vector<string> result;
        
        for (int i=0; i<sizeOfGene; i++)
        {
            char c = gene[i];

            for (char m : mutations[c])
            {
                string possibleGene = gene;              // new copy of the gene
                possibleGene[i] = m;                     // replace c with m
                
                if (bankSet.find(possibleGene) != bankSet.end())
                {
                    // only add the gene if it's in the gene bank
                    result.push_back(possibleGene);
                }   
                
            }   
        }
        return result;
    }
    
    
};
8700