# Using Graph and BFS

• The solution uses graph and breadth first traversal to find the shortest path between the start and the end node. If no such path exists then we return -1.

``````public class Solution {
class Node{
String s;
Node(String s1){
s=s1;
}
}
public int minMutation(String start, String end, String[] bank) {
if(start==null||end==null||start.length()!=8||end.length()!=8){
return -1;
}
if(start.equals(end)){
return 0;
}
Map<String,Node> map = new HashMap<String,Node>();
for(int i=0; i<bank.length; i++){
map.put(bank[i],new Node(bank[i]));
}
Map<String,Boolean> visited = new HashMap<String,Boolean>();
if(!map.containsKey(start)){
map.put(start,new Node(start));
}
for(int i=0; i<bank.length; {
//Everything with a distance of 1 will be considered adjacent nodes.
if(findDistance(start,bank[i])==1){
}
for(int j=i+1; j<bank.length; j++){
if(findDistance(bank[i],bank[j])==1){
}
}
}
q.offer(start);
int level=1,count=0;
while(!q.isEmpty()){
if(level==0){
level=q.size();
count++;
}
String temp=q.poll();
visited.put(temp,true);
if(s1.equals(end)){
return count+1;
}else if(!visited.containsKey(s1)){
}
}

level--;
}
return -1;
}
public int findDistance(String s1, String s2){
int count=0;
for(int i=0; i<s1.length() && count<2; i++){
if(s1.charAt(i)!=s2.charAt(i)){
count++;
}
}
return count;
}
}
``````

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