# DFS java

• ``````class Solution {
// check
// if two seqs only diff in one char it is a valid mutation
// find all the seq has one diff
// get closer to the end.
// keep a explored Set

public int minMutation(String start, String end, String[] bank) {
boolean[] explored = new boolean[bank.length];
if (bank.length == 0) return -1;
return minMutation(explored, start, end,  bank);

}

int minMutation(boolean[] explored, String start, String end, String[] bank) {

if (start.equals(end)) return 0;

int step = bank.length + 1;
for (int i = 0; i < bank.length; i++) {
if (diffOne(start , bank[i]) && ! explored[i]) {
explored[i] = true;
int temp = minMutation(explored, bank[i], end, bank);
if (temp != -1) {
step = Math.min(step, temp);
}
explored[i] = false;
}
}
return step == bank.length + 1 ? -1 : 1 + step;
}

boolean diffOne(String s1, String s2) {
char[] s1c = s1.toCharArray();
char[] s2c = s2.toCharArray();
int count = 0;
for (int i = 0; i < s1c.length; i++) {
if (s1c[i] != s2c[i]) count ++;
if (count >= 2) return false;
}
return count == 1;
}
}
``````

• ``````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);
}
}
}``````

• Why the C++ version cannot pass the OJ, it's exactly the same as your Java version?

``````class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
vector<bool> explored(bank.size(), false);
if (bank.empty()) return -1;
return minMutation(explored, start, end,  bank);
}
bool minMutation(vector<bool>& explored , string start, string end, vector<string>& bank) {
if (start == end) return 0;
int step = bank.size() + 1;
for (int i = 0; i < bank.size(); ++i) {
if (diffOne(start, bank[i]) && explored[i]) {
explored[i] = true;
int temp = minMutation(explored, bank[i], end, bank);
if (temp != -1) {
step = min(step, temp);
}
explored[i] = false;
}
}
return step == bank.size() + 1 ? -1 : 1 + step;
}
bool diffOne(string& s1, string& s2) {
int count = 0;
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i]) ++count;
if (count >= 2) return false;
}
return count == 1;
}
};``````

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