Java solution for word Ladder problem


  • 0
    Y

    Java solution for word Ladder problem

    class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        if(wordList.contains(endWord)==false){
            return 0;
        }
        List<List<String>> graph=ladderLength1(beginWord,endWord,wordList);
    	int distance=BFS(graph,beginWord,endWord);
        
        return distance;
    }
     public static List<List<String>> ladderLength1(String beginWord, String endWord, List<String> wordList) {
    	 
    	   //Create a graph representation to do BFS
           List<String> ls= differByOne(wordList, beginWord);
           List<String> firstWord=new LinkedList<String>();
           
         
           List<List<String>> graph=new ArrayList<List<String>>();
           firstWord.add(beginWord);
           firstWord.addAll(ls);
           graph.add(0, firstWord);
           
           
           for(int i=1;i<=wordList.size();i++) {
        	   List<String> edge=new LinkedList<String>();
        	   List<String> ls2=differByOne(wordList,wordList.get(i-1));
        	   edge.add(wordList.get(i-1));
        	   edge.addAll(ls2);
        	   graph.add(i,edge);
           }
     
          return graph;
    

    }
    //Do BFS

      public static int BFS(List<List<String>> graph, String beginWord,String endWord) {
    	   HashMap<String,Integer> visit=new HashMap<String,Integer>();
    	   int distance=0;
    	   for(int i=0;i<graph.size();i++) {
    		   String vertex=graph.get(i).get(0);
    		   visit.put(vertex,distance);
    	   }
    	  
           Queue<String> queue=new LinkedList<String> ();
           queue.add(beginWord);
      
           visit.put(beginWord,1);
          
           while(!queue.isEmpty()) {
        	       String v=queue.poll();
        	       int index=getIndex(graph,v);
              for(String w: graph.get(index)) {
            	  if (visit.get(w)==0) {
            		  distance=visit.get(v)+1;
            		  queue.add(w);
            		  visit.put(w, distance);
            		  if(w.equals(endWord)){
            			  return distance;
            	  }
              }
           }
           }
           return distance;
        }
     
      public static int getIndex(List<List<String>> graph, String vertex) {
    	  int index=0;
    	  while(index<graph.size()) {
    		  if(graph.get(index).get(0).equals(vertex)) {
    			  break;
    		  }
    		  index++;
    	  }		  
    	  return index;
      }
        
        
     public static List<String> differByOne(List<String> wordList,String beginWord){
            List<String> ls=new ArrayList<String>();
            for(String word: wordList){
            	 int differ=0;
                for(int i=0;i<word.length();i++){
                    if(beginWord.charAt(i)!=word.charAt(i)){
                        differ++;
                    }
                }
                if(differ<=1&&differ>0){
                    ls.add(word);
                }
            }
            return ls;
        }
    

    }


Log in to reply
 

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