<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:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        def checkConnection(gene1,gene2)->bool:
            cnt=0
            for i in range(len(gene1)):
                if gene1[i]!=gene2[i]:
                    cnt+=1
                if cnt>1:
                    return False
            return True
        if endGene not in bank:
            return -1
        maps=collections.defaultdict(lambda:collections.defaultdict(bool))
        for b in bank:
            if checkConnection(startGene,b):
                maps[startGene][b]=True
                maps[b][startGene]=True
            if checkConnection(endGene,b):
                maps[endGene][b]=True
                maps[b][endGene]=True
        for i in range(len(bank)):
            for j in range(i+1,len(bank)):
                if checkConnection(bank[i],bank[j]):
                    maps[bank[i]][bank[j]]=True
                    maps[bank[j]][bank[i]]=True
        cnt=0
        marks={k:-1 for k in maps.keys()} # -1 for to be visited, 0 for visiting, 1 for visited
        def bfs(startSet,depth)->int:
            nonlocal maps
            nex=[]
            while startSet:
                cur=startSet.pop()
                for k,v in maps[cur].items():
                    if marks[k]==-1:
                        if k==endGene:
                            return depth
                        marks[k]=1
                        nex.append(k)
            if not nex:
                return -1
            return bfs(nex,depth+1)
        marks[startGene]=1
        return bfs([startGene],1)
16600