word Ladder, Java - rextester

word Ladder

//'main' method must be in a class 'Rextester'.
//Compiler version 1.8.0_111

import java.util.*;
import java.lang.*;
import javafx.util.Pair;

class Rextester
{  
    public static void main(String args[])
    {
        System.out.println("Hello, World!");

System.out.println(ladderLength("hit","cog",new ArrayList<String>(Arrays.asList("hot","dog","dot","lot","log","cog"))));
    }
    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //create transformations
        int len = beginWord.length();
        Map<String,ArrayList<String>> transformations = new HashMap<String,ArrayList<String>>();

for(String word:wordList){
            for(int i=0;i<len;i++){
                String transform = word.substring(0,i)+"*"+word.substring(i+1,len);
                
                ArrayList<String> lst = transformations.getOrDefault(transform,new ArrayList<String>());
                lst.add(word);
                transformations.put(transform,lst);
            }
        }

Set<String> visited = new HashSet<String>();
        Queue<Pair<String,Integer>> q = new LinkedList<Pair<String,Integer>>();
        
        //enqueue words
        q.add(new Pair(beginWord,1));

visited.add(beginWord);
        while(!q.isEmpty()){
            Pair<String,Integer> pair = q.remove();
            String newWord = pair.getKey();
            int level = pair.getValue();

//find transformations of this word and enqueue corresponding words.
            for(int i = 0;i<len;i++){
                String transform = newWord.substring(0,i)+"*"+newWord.substring(i+1,len);
                for(String word:transformations.getOrDefault(transform,new ArrayList<>())){
                    if(word.equals(endWord))
                        return level+1;
                    if(!visited.contains(word)){
                        visited.add(word);
                        q.add(new Pair(word,level+1));
                    }
                }
            }      
        }
        return 0;
    }
}


run \| edit \| history \| help	0