# Java Solution using Dijkstra's shortest path algorithm

• ``````public class Solution {
public int minMutation(String start, String end, String[] bank) {
int n = bank.length + 1;

String[] banks = new String[n];
banks[0] = start;
System.arraycopy(bank, 0, banks, 1, bank.length);

int[] dis = new int[n];
for (int i = 0; i < n; i++) {
dis[i] = -1;
}
boolean[] vis = new boolean[n];
dis[0] = 0;

for (int i = 0; i < n; i++) {
int minPos = 0;
int minDis = Integer.MAX_VALUE;
for (int j = 0; j < n; j++) {
if (!vis[j] && dis[j] != -1 && minDis > dis[j]) {
minPos = j;
minDis = dis[j];
}
}

vis[minPos] = true;
for (int j = 0; j < n; j++) {
if (!vis[j] && canVisit(banks, minPos, j)) {
if (dis[j] == -1) dis[j] = dis[minPos] + 1;
else dis[j] = Math.min(dis[minPos] + 1, dis[j]);
}
}
}

for (int i = 0; i < n; i++) {
if (dis(banks[i], end) == 0) return dis[i];
}
return -1;
}

private boolean canVisit(String[] banks, int i, int j) {
return dis(banks[i], banks[j]) == 1;
}

private int dis(String a, String b) {
int cnt = 0;
for (int p = 0; p < 8; p++) {
if (a.charAt(p) != b.charAt(p)) cnt++;
}
return cnt;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.