Java 2ms BackTracking solution.

• Hi all,
I tried to solve this problem using backtracking as an exercise.
What do you think?

``````public class Solution {
public int minMutation(String start, String end, String[] bank) {
if(start.length()!=end.length()) return -1;
if(start==end) return 0;

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

int min = Integer.MAX_VALUE;
for(String s: bank){
if(dist(start,s)>1) continue;
min = Math.min(min, minMutation(s,end,bank,set,0));
set.remove(s);
}

if(min==Integer.MAX_VALUE) return -1;
return min;
}

public int minMutation(String current, String end, String[] bank, Set<String> set, int depth){
if(current.equals(end)) return 1;
int min = Integer.MAX_VALUE;

if(depth>=end.length()) return min;

for(String s: bank){
int diff=dist(current,s);
if(!set.contains(s) && (diff==1)){
int num = minMutation(s,end,bank,set,depth+1);
min = Math.min(min, num);
set.remove(s);
}
}
if(min==Integer.MAX_VALUE)
return min;
return 1+min;
}

// counts the distance between two strings
public int dist(String start, String end){
if(start.length()!=end.length()) return Integer.MAX_VALUE;
int diff = 0;
for(int i=0; i<start.length(); i++){
if(start.charAt(i)!=end.charAt(i)) diff++;
}
return diff;
}
}
``````

• @15daniel10 I improved a little bit based on your solution. See detail below:

``````public class RefMinimumGeneticMutation implements Solution {
public int minMutation(String start, String end, String[] bank) {
if (start == null || end == null || bank == null || bank.length == 0 || start.length() != end.length())
return -1;
if (start.equals(end)) return 0;
return minMutation(start, end, bank, new HashSet<String>(), 0);
}

private int minMutation(String current, String end, String[] bank, Set<String> path, int depth) {
int min = -1;
if (current.equals(end)) return 0;
if (depth >= end.length()) return min;
for (String gene : bank) {
if (!path.contains(gene) && isClose(current, gene)) {
int num = minMutation(gene, end, bank, path, depth++);
if (num != -1)
min =  Math.min(Integer.MAX_VALUE, num + 1);
path.remove(gene);
}
}
return min;
}

//check dist is ONE
private boolean isClose(String a, String b) {
if (a.length() != b.length()) return false;
for (int i = 0, diffs=0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i) && ++diffs > 1) return false;
}
return true;
}
}
``````

• @laqxs that's nice!
You removed a lot of duplicated code that I wrote:)

But, I think you maybe have a small 'problem' at you're solution.
`min = Math.min(Integer.MAX_VALUE, num + 1)` will never return MAX_VALUE I think.
In my solution, I added the MAX_VALUE to check if there is any problem inside the recursion.. I think you just worked around it and don't really need to use it at all..

Am I right?

• @15daniel10 Yes, my solution does not return MAX_VALUE. It either return -1 directly or actual min mutations. That's another change I made according to your solution :)

• @laqxs so here:

``````if (num != -1)
min =  Math.min(Integer.MAX_VALUE, num + 1);
path.remove(gene);
``````

you can just assign min to num+1 :)

• @15daniel10 Yes, it works. I forgot that the code already checked if (num!=-1).

• If there were two possible paths from the start string to the end string, and one path was longer than the other, wouldn't this return the longer sub-optimal path if it was encountered first?

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