package com.jbjares.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;


//Given two words (beginWord and endWord),
//and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:

//Only one letter can be changed at a time
//Each intermediate word must exist in the dictionary
//For example,
//
//Given:
//start = "hit"
//end = "cog"
//dict = ["hot","dot","dog","lot","log"]
//As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
//return its length 5.
//
//Note:
//Return 0 if there is no such transformation sequence.
//All words have the same length.
//All words contain only lowercase alphabetic characters.

public class WordLadder {

    public static void main(String[] args) {



        String start = "hit";
        String end = "cog";

        LinkedList<String> dictLinkedList = new LinkedList<String>();
        LinkedList<String> resultLinkedList = new LinkedList<String>();
        dictLinkedList.addAll(Arrays.asList(new String[]{"hot","dot","dog","lot","log"}));


        for(int i=0;i<dictLinkedList.size();i++){
            String actualWord = dictLinkedList.get(i);

            for(char c = 'a';c<='z';c++){
                char[] charArray = actualWord.toCharArray();
                String testOne = new String(charArray[0]+""+c+""+charArray[2]);
                String testTwo = new String(c+""+charArray[1]+""+charArray[2]);
                String testThree = new String(charArray[0]+charArray[1]+c+"");

                if(dictLinkedList.contains(testOne)){
                    resultLinkedList.add(testOne);
                }
                if(dictLinkedList.contains(testTwo)){
                    resultLinkedList.add(testTwo);
                }
                if(dictLinkedList.contains(testThree)){
                    resultLinkedList.add(testThree);
                }

                if(start.equals(testOne) || start.equals(testTwo) ||  start.equals(testThree)){
                    resultLinkedList.addFirst(start);
                }
                if(end.equals(testOne) || end.equals(testTwo) ||  end.equals(testThree)){
                    resultLinkedList.addLast(end);
                }
            }
        }

        Set<String> resultSet = new HashSet<String>();
        resultSet.addAll(resultLinkedList);
        System.out.println(resultSet);
        System.out.println(resultSet.size());
    }



}