Word Ladder hard

Problem Statement

Given two words, beginWord and endWord, and a dictionary wordList, return the length of the 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 wordList.

If there is no such transformation sequence, return 0.

Example 1

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog"

Example 2

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Steps

1. Initialization: Add beginWord to a queue queue and create a visited set to track visited words. Initialize the transformation sequence length level to 1.

2. Breadth-First Search (BFS): While the queue is not empty:

   • Dequeue a word currentWord from the queue.
   • For each word in the wordList, check if it's one letter different from currentWord.
   • If it's different by one letter and not visited:
     • If it's the endWord, return level + 1.
     • Otherwise, mark it as visited and enqueue it.

3. No Transformation: If the queue becomes empty without finding endWord, it means there is no transformation sequence, so return 0.

Explanation

The problem is a classic graph traversal problem. We can represent the words as nodes in a graph, and an edge exists between two nodes if they differ by only one letter. We use BFS because it guarantees finding the shortest path (transformation sequence). The visited set prevents cycles and ensures that we explore each word only once.

Code

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(beginWord);
        visited.add(beginWord);
        int level = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String currentWord = queue.poll();
                for (String word : wordList) {
                    if (diffByOne(currentWord, word) && !visited.contains(word)) {
                        if (word.equals(endWord)) {
                            return level + 1;
                        }
                        queue.offer(word);
                        visited.add(word);
                    }
                }
            }
            level++;
        }
        return 0; // No transformation sequence found
    }

    private boolean diffByOne(String word1, String word2) {
        int diff = 0;
        for (int i = 0; i < word1.length(); i++) {
            if (word1.charAt(i) != word2.charAt(i)) {
                diff++;
            }
        }
        return diff == 1;
    }
}

Complexity

• Time Complexity: O(M * N), where M is the length of the words and N is the number of words in wordList. In the worst case, we might need to explore all words in the wordList.
• Space Complexity: O(N), where N is the number of words in wordList. The visited set and the queue can store up to all the words.