import java.util.*;

public class WordLadder {

	//Bi-directional BFS + memoization, Time O(s*d), Space O(s*d), 
	//s is string length, d is number of steps
	public static int wordLadderLength(String s, String t, List<String> wordList) {
	   if (!wordList.contains(t)) 
		   return 0;
	    Set<String> dict = new HashSet<>(wordList);
	    Set<String> start = new HashSet<>();
	    Set<String> end = new HashSet<>();
	    Set<String> visited = new HashSet<>(); //works as memoization
	    start.add(s); end.add(t);
	    int step = 1;   
	    while (!start.isEmpty() && !end.isEmpty()) {
	        if (start.size() > end.size()) { //start always has smaller set 
	            Set<String> tmp = start;
	            start = end;
	            end = tmp; 
	        }
	       
	        Set<String> tmp = new HashSet<>();
	        for (String word : start) {
	            char[] ch = word.toCharArray();
	            for (int i = 0; i < ch.length; i++) {
	                for (char c = 'a'; c <= 'z'; c++) { //constant time
	                    char origC = ch[i];  
	                    ch[i] = c; //replace c with all other letters in alphabet
	                    String next = String.valueOf(ch);
	                    if (end.contains(next)) 
	                        return step + 1;
	                    if (!visited.contains(next) && dict.contains(next)) {
	                    	System.out.println(next);
	                        tmp.add(next);
	                        visited.add(next);
	                    }
	                    ch[i] = origC;
	                }
	            }
	        }
	        System.out.println(tmp);
	       
	        start = tmp;
	        step++;
	    }
	    return 0;
	}

	public static void main(String args[]) {
		List<String> words = Arrays.asList("cat", "bat", "bet", "bot", "bog", "dog" );
		String s = "cat";
		String t = "dog";
		System.out.println("Dictinary: " + words);
		System.out.println("Start: '" + s + "', end: '" + t + "'");
		System.out.println("Length of word ladder: " + wordLadderLength(s, t, words));;
		System.out.println();
	}
}