class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: list[str]) -> int:
        if endGene not in bank: return -1
        que = []
        front = -1
        tail = -1
        def push_back(que, front, tail, ele):
            tail += 1
            if tail >= len(que):
                que.append(ele)
            else:
                que[tail] = ele
            return tail
        def pop(que, front ,tail):
            front += 1
            return (front , que[front])
        tail = push_back(que,front,tail,(startGene,0))
        def diff(str1, str2) -> int:
            rlt = 0
            for idx, ch in enumerate(str1):
                if(str1[idx] != str2[idx]): rlt += 1
            return rlt
        rlt = 1e5
        while front != tail:
            (front, top_ele) = pop(que, front, tail)            
            step = top_ele[1]
            string = top_ele[0]
            if diff(string, endGene) == 0: return step
            for s in bank:
                diff_num = diff(s, string)
                # print(diff_num)
                if diff_num == 1:
                    tail = push_back(que, front, tail, (s, step + 1))
        return -1

sol = Solution()
print(sol.minMutation("AACCGGTT","AACCGGTA",["AACCGGTA"]))
print(sol.minMutation("AACCGGTT","AAACGGTA",["AACCGGTA","AACCGCTA","AAACGGTA"]))