Word Ladder

shriyanshi24jindal

Mar 29th, 2026

122

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 12.12 KB | None | 0 0

copy raw download clone embed print report

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

RAW Paste Data Copied

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