<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>

// based on the test case
// endGene must come from the bank

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        if(startGene == endGene)
            return 0;
        
        sort(bank.begin(), bank.end());

        auto cmp = [](auto& left, auto& right) {return left.first > right.first;};  // make priority_queue a min-heap
        priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> que(cmp);
        
        vector<bool> visited(bank.size(), false);

        mutate_and_push(bank, visited, startGene, 0, que);

        while(! que.empty()) {
            auto [step, gene_id] = que.top();
            que.pop();
            const string& gene = bank[gene_id];
            
            if(gene == endGene)
                return step;

            mutate_and_push(bank, visited, gene, step, que);
        }

        return -1;
    }

    void mutate_and_push(const vector<string>& bank, vector<bool>& visited, const string& gene, int step, auto& que) {
        const string letter("ACGT");
        for(int i = 0; i < gene.length(); ++i) {
            string mutation = gene;
            for(int j = 0; j < letter.length(); ++j) {
                if(gene[i] != letter[j]) {
                    mutation[i] = letter[j];
                    int id= findMutation(bank, mutation);
                    if(id != bank.size() && visited[id] == false) {
                        que.push(make_pair(step+1,id));
                        visited[id] = true;
                    }
                }
            }
        }
    }

    int findMutation(const vector<string>& bank, const string& mutation) {
        for(int i = 0; i < bank.size(); ++i) {
            if(bank[i] == mutation)
                return i;
        }
        return bank.size();
    }
};
8000