Word Ladder | Leetcode

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

1. Only one letter can be changed at a time
2. 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.

---

Solution: Perform a Breadth-First Search (BFS) by using a queue to hold the nodes. For each word, for each character, iterate from 'a' to 'z' to form all possible next words from the current word. For each next possible word, if it were found in the dictionary, then append it to the queue, with a cost of one more than the current cost.

The key is to remove words from the dictionary as you encounter them. This will ensure that you will not get into an infinite loop.

public class Solution {
    private static class WordNode {
        private String word;
        private int cost;
        
        private WordNode(String word, int cost) {
            this.word = word;
            this.cost = cost;
        }
    }
    
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        if (beginWord.equals(endWord)) return 1;

        LinkedList<WordNode> queue = new LinkedList<>();
        queue.add(new WordNode(beginWord, 1));

        do {
            WordNode wordNode = queue.removeFirst();
            char[] a = wordNode.word.toCharArray();

            for (int i = 0; i < a.length; i++) {
                char savedChar = a[i];

                for (char ch = 'a'; ch <= 'z'; ch++) {
                    if (ch == savedChar) continue;
                    a[i] = ch;
                    String newWord = new String(a);
                    if (newWord.equals(endWord)) return wordNode.cost + 1;
                    if (wordDict.contains(newWord)) {
                        queue.addLast(new WordNode(newWord, wordNode.cost + 1));
                        wordDict.remove(newWord);
                    }
                }

                a[i] = savedChar;
            }
        } while (!queue.isEmpty());

        return 0;
    }
}