word Ladder, Java - rextester

word Ladder

Language: Layout:

//'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;
    }
}

[ + ] Show input
Compilation time: 0.73 sec, absolute running time: 0.17 sec, cpu time: 0.13 sec, memory peak: 20 Mb, absolute service time: 1,02 sec

edit mode | history | discussion

Error(s), warning(s):

source_file.java:36: warning: [rawtypes] found raw type: Pair
        q.add(new Pair(beginWord,1));
                  ^
  missing type arguments for generic class Pair<K,V>
  where K,V are type-variables:
    K extends Object declared in class Pair
    V extends Object declared in class Pair
source_file.java:36: warning: [unchecked] unchecked call to Pair(K,V) as a member of the raw type Pair
        q.add(new Pair(beginWord,1));
              ^
  where K,V are type-variables:
    K extends Object declared in class Pair
    V extends Object declared in class Pair
source_file.java:36: warning: [unchecked] unchecked method invocation: method add in interface Queue is applied to given types
        q.add(new Pair(beginWord,1));
             ^
  required: E
  found: Pair
  where E is a type-variable:
    E extends Object declared in interface Queue
source_file.java:36: warning: [unchecked] unchecked conversion
        q.add(new Pair(beginWord,1));
              ^
  required: E
  found:    Pair
  where E is a type-variable:
    E extends Object declared in interface Queue
source_file.java:52: warning: [rawtypes] found raw type: Pair
                        q.add(new Pair(word,level+1));
                                  ^
  missing type arguments for generic class Pair<K,V>
  where K,V are type-variables:
    K extends Object declared in class Pair
    V extends Object declared in class Pair
source_file.java:52: warning: [unchecked] unchecked call to Pair(K,V) as a member of the raw type Pair
                        q.add(new Pair(word,level+1));
                              ^
  where K,V are type-variables:
    K extends Object declared in class Pair
    V extends Object declared in class Pair
source_file.java:52: warning: [unchecked] unchecked method invocation: method add in interface Queue is applied to given types
                        q.add(new Pair(word,level+1));
                             ^
  required: E
  found: Pair
  where E is a type-variable:
    E extends Object declared in interface Queue
source_file.java:52: warning: [unchecked] unchecked conversion
                        q.add(new Pair(word,level+1));
                              ^
  required: E
  found:    Pair
  where E is a type-variable:
    E extends Object declared in interface Queue
8 warnings

Hello, World!
5

λ

                                      .NET NoSQL database for rapid development