433. 最小基因变化 （ 经典 BFS 广度优先遍历 ）

文章目录

• Question
• Ideas
• • 1、Answer( Java ) - 经典 BFS
  • • Code

Question

433. 最小基因变化

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-genetic-mutation/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

Ideas 1、Answer( Java ) - 经典 BFS

解法思路：经典 BFS

👍注意事项：每一次基因变化只能有一个字符发生了 合法 变化（ 合法 ：即由 start 变为 end 的每一次基因变化中间结果都应该在基因库 bank 中找到）
⚡️举个栗子

//由 start 到 end 的中间一次基因变化结果 AACCGGTA 能在 bank 中找到，故能合法完成基因变化
start = "AACCGGTT"  
end   = "AAACGGTA"
bank  = ["AACCGGTA","AACCGCTA","AAACGGTA"]

Code

/**
 * @author Listen 1024
 * @description  433. 最小基因变化 (经典 BFS )
 * 时间复杂度 O( C×n×m )
 * 空间复杂度 O( n×m )
 * @date 2022-05-07 0:40
 */
class Solution {
    public int minMutation(String start, String end, String[] bank) {
        HashSet<String> set = new HashSet<>();
        HashSet<String> visited = new HashSet<>();
        char[] keys = {'A', 'C', 'G', 'T'};
        for (String s : bank) {
            set.add(s);
        }
        if (start == end) {
            return 0;
        }
        if (!set.contains(end)) {
            return -1;
        }
        int res = 1;
        Queue<String> deque = new ArrayDeque<>();
        deque.offer(start);
        visited.add(start);
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                String curr = deque.poll();
                for (int j = 0; j < 8; j++) {
                    for (int k = 0; k < 4; k++) {
                        if (curr.charAt(j) != keys[k]) {
                            StringBuilder sb = new StringBuilder(curr);
                            sb.setCharAt(j, keys[k]);
                            String s = sb.toString();
                            if (set.contains(s) && !visited.contains(s)) {
                                if (s.equals(end)) {
                                    return res;
                                }
                                deque.offer(s);
                                visited.add(s);
                            }
                        }
                    }
                }
            }
            res++;
        }
        return -1;
    }
}

//部分题解参考链接(如侵删)
https://leetcode.cn/problems/minimum-genetic-mutation/solution/zui-xiao-ji-yin-bian-hua-by-leetcode-sol-lhwy/