Using Graph and BFS


  • 0
    M

    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;
            List<String> adj = new LinkedList<String>();
            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){
                    map.get(start).adj.add(bank[i]);
                    map.get(bank[i]).adj.add(start);
                }
                for(int j=i+1; j<bank.length; j++){
                    if(findDistance(bank[i],bank[j])==1){
                        map.get(bank[i]).adj.add(bank[j]);
                        map.get(bank[j]).adj.add(bank[i]);
                    }   
                }
            }
            Queue<String> q = new LinkedList<String>();
            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);
                for(String s1:map.get(temp).adj){
                    if(s1.equals(end)){
                        return count+1;
                    }else if(!visited.containsKey(s1)){
                        q.add(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;
        }
    }
    

Log in to reply
 

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