class Pair
{
    String word;
    int step;

    Pair(String word, int step)
    {
        this.word = word;
        this.step = step;
    }
}

class Solution {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // Step-1 Storing unique words from word list into set data structure
        HashSet<String> set = new HashSet<>();
        for(String word: wordList)
            set.add(word);

        // Step-2 suppose endword itself is not present in wordlist then return NO PATH FOUND
        if(!set.contains(endWord))
            return 0;
        
        // Step-2 Define a queue and store the <word, step>, we will start with beginWord with step taken as 1
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(beginWord, 1));

        // Step-4 Process the words stored in Queue
        while(!q.isEmpty())
        {
            Pair pair = q.poll();
            String word = pair.word;
            int step = pair.step;

            // if we have reached the end word then return the steps taken to reach end word
            if(word.equals(endWord))
                return step;

            // suppose word is "hit"
            // traversing through each character
            // and see if new word exists in set or not
            for(int i=0; i<word.length(); i++)
            {
                // we will try to change the letter from 'a' to 'z'
                for(char ch='a'; ch<='z';ch++)
                {
                    char[] replacedCharArray = word.toCharArray();
                    replacedCharArray[i] = ch;
                    String newWord = new String(replacedCharArray);

                    // when newWord is present in set then add it to queue 
                    // and remove that from set
                    if(set.contains(newWord))
                    {
                        // If we don’t remove a word after adding it to the queue, it could be visited again later through a different path.
                        set.remove(newWord);
                        q.add(new Pair(newWord, step+1));
                    }

                }
            }
        }
        return 0;
    }
}



// bat, bag, sag, dag, dot
// q: { (cat, 1) }

// c,a,t -> a,a,t -> b,a,t -> c,b,t... -> ca,a....
// q: { (bat, 2) }
// b,a,t -> a,a,t..-> b,b,t...-> ba,g
// q: { (bag, 3) }
// b,a,g -> a,a,g...s,a,g
// q: { (sag, 4) }
// s,a,g --> endWord return steps