This Java program demonstrates how to solve the Word Ladder problem using the Breadth-First Search (BFS) algorithm. The goal is to find the shortest path from a start word to an end word, changing only one letter at a time, with all intermediate words being valid.

Java Code

import java.util.*;

public class WordLadder {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList);
        if (!wordSet.contains(endWord)) {
            return 0;
        }

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int level = 1;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                String currentWord = queue.poll();
                char[] wordChars = currentWord.toCharArray();
                for (int j = 0; j < wordChars.length; j++) {
                    char originalChar = wordChars[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (wordChars[j] == c) continue;
                        wordChars[j] = c;
                        String newWord = new String(wordChars);
                        if (newWord.equals(endWord)) {
                            return level + 1;
                        }
                        if (wordSet.contains(newWord)) {
                            queue.offer(newWord);
                            wordSet.remove(newWord);
                        }
                    }
                    wordChars[j] = originalChar;
                }
            }
            level++;
        }
        return 0;
    }

    public static void main(String[] args) {
        WordLadder solver = new WordLadder();
        List<String> wordList = Arrays.asList("hot","dot","dog","lot","log","cog");
        int ladderLength = solver.ladderLength("hit", "cog", wordList);
        System.out.println("Ladder Length: " + ladderLength);
    }
}

Explanation of the Code

The program defines a class WordLadder with a method ladderLength that implements the BFS algorithm to solve the problem:

• Initialization: A set of words is created from the word list for quick lookup, and a queue is used to hold each level of words to explore.
• BFS Implementation: The BFS starts from the beginWord, exploring all possible one-letter transformations. If a valid transformation is found and is the endWord, the path length is returned. If the transformation is a valid word but not the endWord, it is added to the queue for further exploration.
• Termination: If the endWord is reached, the function returns the length of the path. If the queue is exhausted without finding the endWord, it returns 0, indicating no possible transformation sequence.

This method efficiently explores possible transformations by systematically exploring each level (word distance from the start) before moving on to the next, ensuring the shortest path is found.