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, 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;
}
}