# Java Solution using BFS

• ``````public class Solution {
public int minMutation(String start, String end, String[] bank) {
if(start.equals(end)) return 0;

Set<String> bankSet = new HashSet<>();

char[] charSet = new char[]{'A', 'C', 'G', 'T'};

int level = 0;
Set<String> visited = new HashSet<>();
queue.offer(start);

while(!queue.isEmpty()) {
int size = queue.size();
while(size-- > 0) {
String curr = queue.poll();
if(curr.equals(end)) return level;

char[] currArray = curr.toCharArray();
for(int i = 0; i < currArray.length; i++) {
char old = currArray[i];
for(char c: charSet) {
currArray[i] = c;
String next = new String(currArray);
if(!visited.contains(next) && bankSet.contains(next)) {
queue.offer(next);
}
}
currArray[i] = old;
}
}
level++;
}
return -1;
}
}
``````

• This post is deleted!

• This post is deleted!

• What is the runtime for this in time and space?

• I arrived at a very similar solution except this can be slightly speedier if you test for 'end' when you generate new candidates. My solution solves all tests in 3ms.

``````    public int minMutation(String start, String end, String[] b) {
char[] AGCT = {'A', 'G', 'C', 'T'};
Set<String> closed = new HashSet<>();
Set<String> bank = new HashSet<>();
for (String s : b) bank.add(s);
open.offer(start);
int depth = 0;

while (!open.isEmpty()) {
Queue<String> layer = open;
while (!layer.isEmpty()) {
String next = layer.poll();
char[] chars = next.toCharArray();
for (int i=0; i<chars.length; i++) {
char c = chars[i];
for (char n : AGCT) {
if (c != n) {
chars[i] = n;
String s = new String(chars);
if (!closed.contains(s) && bank.contains(s)) {
if (s.equals(end)) {
return depth+1;
}
open.offer(s);
}
}
}
chars[i] = c;
}
}
depth++;
}
return -1;
}``````

• brilliant solution.

• Thanks for the nice solution!!

I have a question about time complexity.

I thought time complexity was O(N * N * M * K) where:

• N is length of start string
• M is number of letters in gene
• K is number of strings in bank

My thinking ways were:

• We are generating mutations by changing each letter in start string. Then, We will have O(N * M) mutations.
• Generating a mutation takes O(N) because of toCharArray() and new String()
• We will add at most O(K) mutations into queue and there is no duplicate because of set

What do you think about time complexity?

• My DFS Solution.
What I do here is just compare each word in bank with start, and if the difference is just 1, then I'll add that word to set, and move to the next set of words, making that word as start.

``````public int minMutation(String start, String end, String[] bank) {
recurse(start, end, bank, 0, new HashSet<String>());
return count == Integer.MAX_VALUE ? -1 : count;
}
int count = Integer.MAX_VALUE;
private void recurse(String start, String end, String[] bank, int soFar, Set<String> visited) {
if(start.intern() == end.intern()) {
count = Math.min(count, soFar);
}

for(String e : bank) {
int diff = 0;
for(int i = 0; i < e.length(); i++) {
if(start.charAt(i) != e.charAt(i)) {
diff++;
if(diff > 1) break;
}
}
if(diff == 1 && !visited.contains(e)) {
recurse(e, end, bank, soFar+1, visited);
visited.remove(e);
}
}
}``````

• what's the reasoning behind this:

int size = queue.size();
while(size-- > 0) { ... }

• @wavy It is pretty precise and straightforward! And the running time is impressive

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