Word Ladder

Solution For Word Ladder

The Word Ladder problem on LeetCode requires you to find the shortest path from a given start word to a given end word by changing one letter at a time, such that every intermediate word is also a valid word from a given word list.

A valid word list is provided as input, and the start and end words are also given. Your task is to determine the number of steps required to reach the end word from the start word, where each step involves changing one letter at a time.

To solve this problem, we can follow these steps:

  1. Initialize a queue that will store our intermediate words.
  2. Add the start word to the queue.
  3. Initialize a visited set to keep track of the words we have already visited.
  4. Add the start word to the visited set.
  5. Initialize a step count to keep track of the number of steps required to reach the end word.
  6. While the queue is not empty, do the following:

    • Remove the first word from the queue.
    • For each character in the word, replace it with a different letter of the alphabet, and check if the resulting word is in the word list and not in the visited set.
    • If the resulting word is the end word, return the current step count + 1.
    • If the resulting word is valid, add it to the queue and the visited set.
    • Repeat this process until the queue is empty.
  7. If we reach the end word without finding it, return 0.

Here is the Python code that implements this solution:

“`
from collections import deque

class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
wordSet = set(wordList)
if endWord not in wordSet:
return 0

    queue = deque([(beginWord, 1)])
    visited = set()

    while queue:
        word, step = queue.popleft()

        if word == endWord:
            return step

        for i in range(len(word)):
            for c in "abcdefghijklmnopqrstuvwxyz":
                newWord = word[:i] + c + word[i+1:]
                if newWord in wordSet and newWord not in visited:
                    queue.append((newWord, step+1))
                    visited.add(newWord)

    return 0

“`
The time complexity of this solution is O(M^2 * N), where M is the length of the words and N is the size of the word list. The space complexity of this solution is also O(M^2 * N) due to the use of the queue and visited set.

Step by Step Implementation For Word Ladder

import java.util.*; 
public class Solution {
    public int ladderLength(String beginWord, String endWord, List wordList) {
        // edge case
        if (!wordList.contains(endWord)) {
            return 0;
        }
        
        // use a queue to do a BFS
        Queue queue = new LinkedList<>();
        queue.add(beginWord);
        int level = 0;
        
        // keep track of visited words
        Set visited = new HashSet<>();
        visited.add(beginWord);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curr = queue.poll();
                if (curr.equals(endWord)) {
                    return level + 1;
                }
                for (int j = 0; j < curr.length(); j++) {
                    char[] chars = curr.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        chars[j] = c;
                        String temp = new String(chars);
                        if (!visited.contains(temp) && wordList.contains(temp)) {
                            queue.add(temp);
                            visited.add(temp);
                        }
                    }
                }
            }
            level++;
        }
        return 0;
    }
}
from collections import defaultdict 
  
class Graph: 
  
    def __init__(self): 
        self.graph = defaultdict(list) 
  
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    def BFS(self, s, t): 
  
        if s == t: 
            return True
  
        visited = [False] * (len(self.graph)) 
        queue = [] 
  
        queue.append(s) 
        visited[s] = True
  
        while queue: 
  
            u = queue.pop(0) 
  
            for i in self.graph[u]: 
                if visited[i] == False: 
                    queue.append(i) 
                    visited[i] = True
        return visited[t] 
  
g = Graph() 
g.addEdge(0, 1) 
g.addEdge(0, 2) 
g.addEdge(1, 2) 
g.addEdge(2, 0) 
g.addEdge(2, 3) 
g.addEdge(3, 3) 
  
u = 1; v = 3

if g.BFS(u, v) == True: 
    print("There is a path from %d to %d" % (u,v)) 
else : 
    print("There is no path from %d to %d" % (u,v))
var ladderLength = function(beginWord, endWord, wordList) {
    if (!wordList.includes(endWord)) {
        return 0;
    }
    
    let queue = [beginWord];
    let seen = new Set([beginWord]);
    let steps = 0;
    
    while (queue.length > 0) {
        steps++;
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let word = queue.shift();
            if (word === endWord) {
                return steps;
            }
            
            for (let j = 0; j < word.length; j++) {
                let newWord = word.slice(0, j) + '*' + word.slice(j + 1);
                if (seen.has(newWord)) continue;
                
                for (let k = 0; k < wordList.length; k++) {
                    if (transform(newWord, wordList[k])) {
                        queue.push(wordList[k]);
                        seen.add(wordList[k]);
                    }
                }
            }
        }
    }
    
    return 0;
};

function transform(word1, word2) {
    let count = 0;
    for (let i = 0; i < word1.length; i++) {
        if (word1[i] !== word2[i]) {
            count++;
        }
    }
    
    return count === 1;
}
This is a C++ solution for the leetcode problem word-ladder. The output should only consist of exact code with comments and nothing else.

1. Create a queue of strings, and enqueue the first word in the list.
2. Create a set to keep track of visited words.
3. While the queue is not empty:
4. Dequeue the first word from the queue.
5. If the word is the target word, return the number of steps it took to reach the target.
6. Otherwise, for each possible transformation of the word:
7. If the transformed word is not in the visited set:
8. Add the transformed word to the visited set.
9. Enqueue the transformed word.
10. Return -1 if the queue is empty, indicating that the target could not be reached.
public class Solution {
    public int LadderLength(string beginWord, string endWord, IList wordList) {
        // Create a queue for BFS
        Queue queue = new Queue();
        // Add the beginWord to the queue
        queue.Enqueue(beginWord);
        // Add 1 to the length of the ladder
        int ladderLength = 1;
        // While the queue is not empty
        while (queue.Count != 0) {
            // Get the size of the queue
            int size = queue.Count;
            // For each element in the queue
            for (int i = 0; i < size; i++) {
                // Dequeue the element
                string word = queue.Dequeue();
                // If the element is the endWord
                if (word == endWord) {
                    // Return the length of the ladder
                    return ladderLength;
                }
                // For each character in the word
                for (int j = 0; j < word.Length; j++) {
                    // Create a char array of the word
                    char[] chars = word.ToCharArray();
                    // For each letter in the alphabet
                    for (char c = 'a'; c <= 'z'; c++) {
                        // If the current character is not the same as the character in the word
                        if (chars[j] != c) {
                            // Swap the characters
                            chars[j] = c;
                            // If the resulting word is in the wordList
                            if (wordList.Contains(new string(chars))) {
                                // Add the word to the queue
                                queue.Enqueue(new string(chars));
                                // Remove the word from the wordList
                                wordList.Remove(new string(chars));
                            }
                        }
                    }
                }
            }
            // Add 1 to the length of the ladder
            ladderLength++;
        }
        // If we get to this point, it means that we were unable to find a ladder
        return 0;
    }
}


Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]