Word Ladder

                                            
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(), wordList.end());
        if (wordSet.find(endWord) == wordSet.end()) {
            return 0;
        }
        
        queue<string> q;
        q.push(beginWord);
        int ladderLength = 1;
        
        while (!q.empty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; ++i) {
                string currentWord = q.front();
                q.pop();
                
                if (currentWord == endWord) {
                    return ladderLength;
                }
                
                for (int j = 0; j < currentWord.length(); ++j) {
                    char originalChar = currentWord[j];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        if (c == originalChar) {
                            continue;
                        }
                        currentWord[j] = c;
                        if (wordSet.find(currentWord) != wordSet.end()) {
                            q.push(currentWord);
                            wordSet.erase(currentWord);
                        }
                    }
                    currentWord[j] = originalChar;
                }
            }
            ++ladderLength;
        }
        
        return 0;
    }
};

                                            
class Solution {
    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 size = queue.size();
            for (int i = 0; i < size; i++) {
                String currentWord = queue.poll();
                char[] wordArray = currentWord.toCharArray();
                for (int j = 0; j < wordArray.length; j++) {
                    char originalChar = wordArray[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (wordArray[j] == c) {
                            continue;
                        }
                        wordArray[j] = c;
                        String newWord = new String(wordArray);
                        if (newWord.equals(endWord)) {
                            return level + 1;
                        }
                        if (wordSet.contains(newWord)) {
                            queue.offer(newWord);
                            wordSet.remove(newWord);
                        }
                    }
                    wordArray[j] = originalChar;
                }
            }
            level++;
        }
        
        return 0;
    }
}

                                            
from collections import deque

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        wordSet = set(wordList)
        if endWord not in wordSet:
            return 0
        
        queue = deque()
        queue.append((beginWord, 1))
        
        while queue:
            currentWord, length = queue.popleft()
            if currentWord == endWord:
                return length
            
            for i in range(len(currentWord)):
                for char in 'abcdefghijklmnopqrstuvwxyz':
                    nextWord = currentWord[:i] + char + currentWord[i+1:]
                    if nextWord in wordSet:
                        wordSet.remove(nextWord)
                        queue.append((nextWord, length+1))
        
        return 0

                                            
public class Solution {
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
        HashSet<string> wordSet = new HashSet<string>(wordList);
        
        if (!wordSet.Contains(endWord)) {
            return 0;
        }
        
        Queue<string> queue = new Queue<string>();
        queue.Enqueue(beginWord);
        
        int level = 1;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            
            for (int i = 0; i < size; i++) {
                string currentWord = queue.Dequeue();
                
                char[] charArray = currentWord.ToCharArray();
                
                for (int j = 0; j < charArray.Length; j++) {
                    char originalChar = charArray[j];
                    
                    for (char c = 'a'; c <= 'z'; c++) {
                        charArray[j] = c;
                        string newWord = new string(charArray);
                        
                        if (newWord.Equals(endWord)) {
                            return level + 1;
                        }
                        
                        if (wordSet.Contains(newWord) && !newWord.Equals(currentWord)) {
                            queue.Enqueue(newWord);
                            wordSet.Remove(newWord);
                        }
                    }
                    charArray[j] = originalChar;
                }
            }
            
            level++;
        }
        
        return 0;
    }
}

                                            
/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
var ladderLength = function(beginWord, endWord, wordList) {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;

    const queue = [[beginWord, 1]];

    while (queue.length) {
        const [word, level] = queue.shift();

        if (word === endWord) {
            return level;
        }

        for (let i = 0; i < word.length; i++) {
            for (let j = 0; j < 26; j++) {
                const newWord = word.slice(0, i) + String.fromCharCode(97 + j) + word.slice(i + 1);

                if (wordSet.has(newWord)) {
                    queue.push([newWord, level + 1]);
                    wordSet.delete(newWord);
                }
            }
        }
    }

    return 0;
};

                                            
function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
    const wordSet = new Set(wordList);
    if (!wordSet.has(endWord)) return 0;

    let queue = [beginWord];
    let level = 1;

    while (queue.length > 0) {
        const nextQueue: string[] = [];

        for (const word of queue) {
            if (word === endWord) return level;

            for (let i = 0; i < word.length; i++) {
                for (let j = 0; j < 26; j++) {
                    const newWord = word.slice(0, i) + String.fromCharCode(97 + j) + word.slice(i + 1);
                    if (wordSet.has(newWord)) {
                        nextQueue.push(newWord);
                        wordSet.delete(newWord);
                    }
                }
            }
        }

        queue = nextQueue;
        level++;
    }

    return 0;
};

                                            
class Solution {
    /**
     * @param String $beginWord
     * @param String $endWord
     * @param String[] $wordList
     * @return Integer
     */
    function ladderLength($beginWord, $endWord, $wordList) {
        $wordSet = array_flip($wordList);
        if (!isset($wordSet[$endWord])) {
            return 0;
        }
        
        $queue = [$beginWord];
        $level = 1;
        
        while (!empty($queue)) {
            $next = [];
            foreach ($queue as $word) {
                for ($i = 0; $i < strlen($word); $i++) {
                    $oldChar = $word[$i];
                    for ($j = 0; $j < 26; $j++) {
                        $word[$i] = chr(97 + $j);
                        if ($word === $endWord) {
                            return $level + 1;
                        }
                        if (isset($wordSet[$word])) {
                            $next[] = $word;
                            unset($wordSet[$word]);
                        }
                    }
                    $word[$i] = $oldChar;
                }
            }
            $queue = $next;
            $level++;
        }
        
        return 0;
    }
}

                                            
class Solution {
    func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
        var wordSet = Set(wordList)
        if !wordSet.contains(endWord) {
            return 0
        }
        
        var queue = [(beginWord, 1)]
        
        while !queue.isEmpty {
            let (word, steps) = queue.removeFirst()
            
            if word == endWord {
                return steps
            }
            
            for i in 0..<word.count {
                var chars = Array(word)
                for char in "abcdefghijklmnopqrstuvwxyz" {
                    chars[i] = char
                    let newWord = String(chars)
                    if wordSet.contains(newWord) {
                        queue.append((newWord, steps + 1))
                        wordSet.remove(newWord)
                    }
                }
            }
        }
        
        return 0
    }
}

                                            
class Solution {
    fun ladderLength(beginWord: String, endWord: String, wordList: List<String>): Int {
        val wordSet = wordList.toMutableSet()
        if (endWord !in wordSet) return 0
        
        var level = 1
        val queue = LinkedList<String>()
        queue.offer(beginWord)
        
        while (queue.isNotEmpty()) {
            val size = queue.size
            repeat(size) {
                val currentWord = queue.poll()
                
                for (i in 0 until currentWord.length) {
                    val wordArray = currentWord.toCharArray()
                    for (c in 'a'..'z') {
                        wordArray[i] = c
                        val newWord = String(wordArray)
                        
                        if (newWord == currentWord) continue
                        if (newWord == endWord) return level + 1
                        if (newWord in wordSet) {
                            queue.offer(newWord)
                            wordSet.remove(newWord)
                        }
                    }
                }
            }
            level++
        }
        
        return 0
    }
}

                                            
func ladderLength(beginWord string, endWord string, wordList []string) int {
    wordSet := make(map[string]bool)
    for _, word := range wordList {
        wordSet[word] = true
    }

    if _, ok := wordSet[endWord]; !ok {
        return 0
    }

    queue := []string{beginWord}
    level := 1

    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            currentWord := queue[0]
            queue = queue[1:]

            if currentWord == endWord {
                return level
            }

            for j := 0; j < len(currentWord); j++ {
                for c := 'a'; c <= 'z'; c++ {
                    newWord := currentWord[:j] + string(c) + currentWord[j+1:]
                    if _, ok := wordSet[newWord]; ok {
                        queue = append(queue, newWord)
                        delete(wordSet, newWord)
                    }
                }
            }
        }
        level++
    }

    return 0
}

                                            
# @param {String} begin_word
# @param {String} end_word
# @param {String[]} word_list
# @return {Integer}
def ladder_length(begin_word, end_word, word_list)
    return 0 if !word_list.include?(end_word)
    
    word_set = Set.new(word_list)
    
    queue = Queue.new
    queue.push([begin_word, 1])
    
    while !queue.empty?
        current_word, length = queue.pop
        
        if current_word == end_word
            return length
        end
        
        (0...current_word.length).each do |i|
            ('a'..'z').each do |char|
                new_word = current_word.dup
                new_word[i] = char
                
                if word_set.include?(new_word)
                    queue.push([new_word, length + 1])
                    word_set.delete(new_word)
                end
            end
        end
    end
    
    return 0
end

                                            
object Solution {
    def ladderLength(beginWord: String, endWord: String, wordList: List[String]): Int = {
        import scala.collection.mutable
        val wordSet = wordList.toSet
        val queue = mutable.Queue[(String, Int)]((beginWord, 1))
        val visited = mutable.Set[String]()

        while (queue.nonEmpty) {
            val (currentWord, level) = queue.dequeue()
            if (currentWord == endWord) {
                return level
            }
            for (i <- 0 until currentWord.length) {
                for (c <- 'a' to 'z') {
                    val newWord = currentWord.updated(i, c)
                    if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                        visited.add(newWord)
                        queue.enqueue((newWord, level + 1))
                    }
                }
            }
        }

        0
    }
}

                                            
impl Solution {
    pub fn ladder_length(begin_word: String, end_word: String, word_list: Vec<String>) -> i32 {
        use std::collections::{HashSet, VecDeque};

        let word_set: HashSet<String> = word_list.into_iter().collect();
        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        queue.push_back((begin_word, 1));

        while let Some((word, steps)) = queue.pop_front() {
            if word == end_word {
                return steps;
            }

            let chars: Vec<char> = word.chars().collect();
            for i in 0..chars.len() {
                let original_char = chars[i];

                for c in 'a'..='z' {
                    if c == original_char {
                        continue;
                    }

                    let mut new_chars = chars.clone();
                    new_chars[i] = c;
                    let new_word: String = new_chars.iter().collect();
                    if word_set.contains(&new_word) && visited.insert(new_word.clone()) {
                        queue.push_back((new_word, steps + 1));
                    }
                }
            }
        }

        0
    }
}

To solve this coding challenge, we need to find the shortest transformation sequence from the

beginWord

to the

endWord

using the words available in the

wordList

. The transformation sequence must follow these rules:

Each step can change only one letter at a time.
All intermediate words must be in the
wordList

.
If the transformation is possible, the function should return the length of the shortest transformation sequence (starting with
beginWord

and ending with
endWord

). If the transformation is not possible, the function should return
0

.

Explanation

The problem is essentially about finding the shortest path in a graph where each word is a node, and an edge exists between two nodes if the corresponding words differ by exactly one letter. We can use the Breadth-First Search (BFS) algorithm, which is well-suited for finding the shortest path in an unweighted graph. Here’s a step-by-step explanation of the approach:

Initial Checks : Check if the
endWord

is in the
wordList

. If not, return
0

immediately because it's not possible to form a sequence without the target word.
BFS Initialization : Use a queue to perform BFS. The queue will store tuples
(currentWord, lengthOfTransformationSequence)

. Initialize the queue with the
beginWord

and a transformation length of
1

.
BFS Loop : While there are elements in the queue, perform the following steps:

Dequeue the front element and extract the
currentWord

and
currentLength

.
If
currentWord

matches the
endWord

, return
currentLength

as it represents the shortest transformation sequence length.
For each character position in the
currentWord

, try replacing it with every letter from
a

to
z

to form a new word.
If the new word is in the
wordList

(which we'll maintain as a set for O(1) lookups), enqueue the new word with an incremented transformation length and remove it from the set to prevent revisiting.

No Valid Transformation : If we exit the loop without having found the
endWord

, return
0

.

Detailed Steps in Pseudocode

Convert
wordList

to a set for faster lookups.
If
endWord

is not in the set, return
0

.
Initialize a queue for BFS with a tuple of
beginWord

and
1

.
While the queue is not empty, do the following:

Dequeue the front element.
If the current word matches
endWord

, return the current length.
For each character position in the current word:

Replace it with every letter from 'a' to 'z'.
If the new word is in the set:

Enqueue the new word with an incremented length.
Remove the new word from the set.

If the loop ends without finding
endWord

, return
0

.

Detailed Steps in Pseudocode

                                            
# Step 1: Convert wordList to a set for faster lookups
wordSet = set(wordList)

# Step 2: If endWord is not in the set, return 0
if endWord not in wordSet:
    return 0

# Step 3: Initialize queue for BFS with a tuple (beginWord, 1)
queue = initialize_queue_with(beginWord, 1)

# Step 4: Start BFS
while queue is not empty:
    # Dequeue the front element
    currentWord, currentLength = dequeue(queue)

    # If currentWord matches endWord, return currentLength
    if currentWord == endWord:
        return currentLength

    # For each character position in currentWord
    for i from 0 to length(currentWord) - 1:
        # For each letter 'a' to 'z'
        for char in 'abcdefghijklmnopqrstuvwxyz':
            # Construct the new word by replacing the character in position i
            newWord = currentWord[0:i] + char + currentWord[i+1:]

            # If newWord is in the set
            if newWord in wordSet:
                # Enqueue newWord with incremented length
                enqueue(queue, (newWord, currentLength + 1))
                # Remove newWord from the set
                wordSet.remove(newWord)

# If loop ends without finding endWord, return 0
return 0

With this detailed approach, we ensure that we explore all possible transformations in a level-by-level manner, which guarantees finding the shortest path if it exists.