class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        // set：用于存储基因库中所有有效的基因序列，提供 O(1) 的快速查找和删除能力
        Set<String> set = new HashSet<>();
        // 将 bank 数组中的所有合法基因序列加入到 set 中
        for (String string : bank) {
            set.add(string);
        }
        
        // 极端条件：如果目标基因 endGene 不包含在基因库中，根本无法达成，直接返回 -1
        if (!set.contains(endGene)) {
            return -1;
        }
        
        // step：记录当前搜索的层数（即基因变化的最少次数）
        int step = 0;
        // xyz：定义基因突变中仅允许出现的 4 个有效字符
        char[] xyz = {'A', 'C', 'G', 'T'};
        // queue：用于 BFS 遍历的队列，存放当前层待尝试变异的基因序列
        Queue<String> queue = new LinkedList<>();
        // 将起始基因序列加入队列
        queue.offer(startGene);

        // BFS 核心循环：只要队列不为空，就持续向外扩散探索
        while (!queue.isEmpty()) {
            // size：记录当前队列中属于同一层级的所有序列数量
            int size = queue.size();
            
            // 遍历当前层的所有节点（按层遍历，保证步数最小）
            for (int i = 0; i < size; i++) {
                // poll：从队列中弹出一个当前的基因序列
                String poll = queue.poll();
                // 将字符串转为字符数组（字符串是不可变的，转为字符数组方便修改单个字符）
                char[] ch = poll.toCharArray();
                
                // 遍历 8 个位置的基因字符
                for (int j = 0; j < 8; j++) {
                    // originalChar：记录当前位的原始字符，用于后续尝试完其他选项后恢复原状
                    char originalChar = ch[j];
                    
                    // 尝试将第 j 位替换为 xyz 中的 4 个字符
                    for (char current : xyz) {
                        // 如果替换的字符和原来一样，则跳过
                        if (current == originalChar) {
                            continue;
                        }
                        
                        // 修改当前位的字符
                        ch[j] = current;
                        // now：将修改后的字符数组转回新的基因序列字符串
                        String now = new String(ch);
                        
                        // 如果经过一次变异，直接得到了目标基因 endGene
                        if (now.equals(endGene)) {
                            return step + 1;
                        }
                        
                        // 如果新生成的基因序列在基因库 set 中，说明这是合法的一步
                        if (set.contains(now)) {
                            // 将其加入到 BFS 的下一层队列中
                            queue.offer(now);
                            // 从 set 中删除该序列，防止后续其他路径重复访问，形成死循环
                            set.remove(now);
                        }
                        
                        // 回溯：恢复第 j 位的原始字符，准备尝试下一个不同的突变字符
                        ch[j] = originalChar;
                    }
                }
            }
            // 当前层的所有节点都探索完毕后，表示完成了一次基因变化，步数加 1
            step++;
        }
        // 如果 BFS 遍历完所有可能都没有找到 endGene，说明无法完成变异，返回 -1
        return -1;
    }
}