# Java Bidirectional Search Solution (faster than BFS)

• Each valid `gene string` can be considered as a `node` of a `graph`, and when two strings has exactly one different char, there is an `edge` connecting these two vertices.

Then, this problem is converted to a `graph problem`: given two vertices (start and end), find the shortest path from one to the other.

We know BFS is faster than DFS for such a scenario.

Here I introduce something theoretically faster than BFS, called `Bidirectional Search`.

From Cracking the Coding Interview, 6th Edition, Page 108:

"Bidirectional search is used to find the shortest path between a source and destination node. It operates by essentially running two simultaneous breadth-first searches, one from each node. When their searches collide, we have found a path. Too see why this is faster, consider a graph where every node has at most k adjacent nodes and the shortest path from node s to node t has length d.

"In traditional breadth-first search, we would search up to k nodes in the first "level" of the search. In the second level, we would search up to k nodes for each of those first k nodes, so k^2 nodes total (thus far). We would do this d times, so that's O(k^d) nodes.

"In bidirectional search, we have two searches that collide after approximately d/2 levels ( the midpoint of the path). The search from s visits approximately k^(d/2), as does the search from t. That's approximately 2k^(d/2), or O(k^(d/2)), nodes total."

Below is a Java implementation:

``````public int minMutation(String start, String end, String[] bank) {
List<Integer>[] graph = new List[bank.length];
for (int i = 0; i < bank.length; i++) {
graph[i] = new ArrayList<>();
for (int j = 0; j < bank.length; j++)
}

int targetIdx = -1;
for (int i = 0; i < bank.length; i++) {
if (bank[i].equals(end)) {targetIdx = i; break;}
}
if (targetIdx == -1) return -1;

// endXXX means something calculated from end to start
int[] endDist = new int[bank.length];
Arrays.fill(endDist, -1);
endDist[targetIdx] = 0;
Queue<Integer> endQ = new ArrayDeque<>();
for (int idx : graph[targetIdx]) {
endDist[idx] = 1;
}

// startXXX means something calculated from start to end
int[] startDist = new int[bank.length];
Arrays.fill(startDist, -1);
Queue<Integer> startQ = new ArrayDeque<>();
for (int i = 0; i < bank.length; i++) {
if (canMutate(start, bank[i])) {
if (bank[i].equals(end)) return 1;
startDist[i] = 1;
}
}

while (!startQ.isEmpty() && !endQ.isEmpty()) {
int startIdx = startQ.poll();
for (int nextIdx : graph[startIdx]) {
if (startDist[nextIdx] != -1) continue;
else if (endDist[nextIdx] >= 0) return startDist[startIdx] + endDist[nextIdx] + 1;
else {
startDist[nextIdx] = startDist[startIdx] + 1;
}
}

int endIdx = endQ.poll();
for (int nextIdx : graph[endIdx]) {
if (endDist[nextIdx] != -1) continue;
else if (startDist[nextIdx] > 0) return startDist[nextIdx] + endDist[endIdx] + 1;
else {
endDist[nextIdx] = endDist[endIdx] + 1;
}
}
}

return -1;
}

private boolean canMutate(String gen1, String gen2) {
int diff = 0;
for (int i = 0; i < gen1.length(); i++)
diff += gen1.charAt(i) == gen2.charAt(i) ? 0 : 1;
return diff == 1;
}

``````

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