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:
- Initialize a queue that will store our intermediate words.
- Add the start word to the queue.
- Initialize a visited set to keep track of the words we have already visited.
- Add the start word to the visited set.
- Initialize a step count to keep track of the number of steps required to reach the end word.
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.
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, ListwordList) { // 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, IListwordList) { // 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; } }