static ArrayList<String> string_transformation(ArrayList<String> words, String start, String stop) {
    if(start == null || (start.equals(stop) && words.size() == 0))
        return new ArrayList<String>(Arrays.asList("-1"));

    HashSet<String> dict = new HashSet<String>(words);
    dict.add(start);
    dict.add(stop);

    // Edge case
    if(start.equals(stop))
    {
        ArrayList<String> result = new ArrayList<String>();
        result.add(start);
        for(String w: dict){
            if(diffOfOne(w, start)){
                result.add(w);
                break;
            }
        }
        result.add(stop);
        return result;
    }

    if(dict.size() < start.length()*26) {
        return bfsWithCompare(dict, start, stop);
    }
    return bfsWithTransform(dict, start, stop );
}



static ArrayList<String> bfsWithCompare(HashSet<String> dict, String start, String stop){

    Queue<String> q = new LinkedList<String>();

    HashMap<String, String> parent = new HashMap<String, String>();

    Set<String> visited = new HashSet();

    ArrayList<String> result = new ArrayList<String>();

    q.add(start);

    visited.add(start);

    parent.put(start, null);



    while(!q.isEmpty()){

       int size = q.size();

        for(int i = 0; i<size ;i++){

            String word = q.poll();

            if( word.equals(stop)) return createResultList(stop, parent);

            for(String w: dict){

                if( !visited.contains(w) && diffOfOne(w, word)){

                    q.add(w);

                    visited.add(w);

                    parent.put(w,word);

                }

            }

        }

    }

    return new ArrayList<>(Arrays.asList("-1"));

}



static ArrayList<String> bfsWithTransform(HashSet<String> dict, String start, String stop){

    Queue<String> q = new LinkedList<String>();

    HashMap<String, String> parent = new HashMap<String, String>();

    Set<String> visited = new HashSet();

    ArrayList<String> result = new ArrayList<String>();

    q.add(start);

    visited.add(start);

    parent.put(start, null);



    if(start.equals(stop)) visited.remove(start);

    while(!q.isEmpty()){

        int size = q.size();



        for(int i = 0; i<size ;i++){

            String word = q.poll();

            if(word.equals(stop)) return createResultList(stop, parent);



            char[] arr = word.toCharArray();

            for(int j = 0; j<arr.length; j++){

                char original = arr[j];

                for( char ch ='a'; ch <= 'z' ; ch++){

                    if(ch == original ) continue;

                    arr[j] = ch;

                    String s = new String(arr);

                    if(!visited.contains(s) && dict.contains(s)){

                        q.add(s);

                        parent.put(s,word);

                        visited.add(s);

                    }

                }

                arr[j] = original;

            }

        }

    }

    return new ArrayList<>(Arrays.asList("-1"));

}



static boolean diffOfOne(String w1, String w2){

    int diff = 0;

    for(int i =0; i< w1.length() ;i++){

        if(w1.charAt(i) != w2.charAt(i)) diff++;

        if(diff>1) return false;

    }

    return true;

}



    static ArrayList<String> createResultList(String stop, HashMap<String, String> parentMap){

    ArrayList<String> result = new ArrayList<String>();

    result.add(stop);

    String parent = parentMap.get(stop);

    while(parent != null){

        result.add(parent);

        parent = parentMap.get(parent);

    }

    Collections.reverse(result);

    return result;

}