Java | Leetcode Java题解之第433题最小基因变化

题目：

题解：

class Solution {public int minMutation(String start, String end, String[] bank) {int m = start.length();int n = bank.length;List<Integer>[] adj = new List[n];for (int i = 0; i < n; i++) {adj[i] = new ArrayList<Integer>();}int endIndex = -1;for (int i = 0; i < n; i++) {if (end.equals(bank[i])) {endIndex = i;}for (int j = i + 1; j < n; j++) {int mutations = 0;for (int k = 0; k < m; k++) {if (bank[i].charAt(k) != bank[j].charAt(k)) {mutations++;}if (mutations > 1) {break;}}if (mutations == 1) {adj[i].add(j);adj[j].add(i);}}}if (endIndex == -1) {return -1;}Queue<Integer> queue = new ArrayDeque<Integer>();boolean[] visited = new boolean[n];int step = 1;for (int i = 0; i < n; i++) {int mutations = 0;for (int k = 0; k < m; k++) {if (start.charAt(k) != bank[i].charAt(k)) {mutations++;}if (mutations > 1) {break;}}if (mutations == 1) {queue.offer(i);visited[i] = true;}}        while (!queue.isEmpty()) {int sz = queue.size();for (int i = 0; i < sz; i++) {int curr = queue.poll();if (curr == endIndex) {return step;}for (int next : adj[curr]) {if (visited[next]) {continue;}visited[next] = true;queue.offer(next);}}step++;}return -1;}
}