Sponsored
Sponsored
The idea is to optimize the BFS by starting the search from both the beginWord and the endWord simultaneously. This bidirectional approach helps in cutting down the search space significantly as the two searches will meet in the middle.
Initially, we create two sets to track words to visit from the beginning side and the ending side. We also use a visited set to ensure we do not revisit any words.
We alternate the search extensions from one side to another to maintain the balance of the search width for the two meet points.
Due to the bidirectional nature, the time complexity can be greatly reduced compared to a conventional BFS.
Time Complexity: O(N * M * 26) where N is the number of words and M is the word length.
Space Complexity: O(N * M) due to the storage of the graph.
1function findLadders(beginWord, endWord, wordList) {
2 const tree = new Map();
3 const wordSet = new Set(wordList);
4 if (!wordSet.has(endWord)) return [];
5 let found = false;
6 let q = new Set([beginWord]);
7 while (q.size && !found) {
8 wordSet.forEach(
9 word => q.has(word) ? wordSet.delete(word) : null
10 );
11 const nextSet = new Set();
12 for (let word of q) {
13 for (let i = 0; i < word.length; i++) {
14 for (let j = 97; j <= 122; j++) {
15 const newWord = word.slice(0, i) + String.fromCharCode(j) + word.slice(i + 1);
16 if (wordSet.has(newWord) || newWord == endWord) {
17 if (!tree.has(word)) tree.set(word, []);
18 tree.get(word).push(newWord);
19 if (newWord == endWord) found = true;
20 nextSet.add(newWord);
21 }
22 }
23 }
24 }
25 q = nextSet;
26 }
27
28 const res = [];
29 function dfs(word, path) {
30 if (word === endWord) {
31 res.push([...path, word]);
32 return;
33 }
34 if (tree.has(word)) {
35 for (let next of tree.get(word)) {
36 dfs(next, [...path, word]);
37 }
38 }
39 }
40 dfs(beginWord, []);
41 return res;
42}This JavaScript code employs a similar strategy using Sets for managing word transformations and a map to track paths during BFS. The DFS helper function then reconstructs all valid paths after the BFS concludes.
Using a single queue BFS, we explore transformations level by level. We build a graph where each word is a node, and edges are valid single-letter transformations as they appear in the word list. During BFS, paths are stored and checked for minimum length.
We mark words visited in the current level to avoid loops and unnecessary processing.
Once a complete path is found its length is compared to ensure it’s the smallest, and added to results if valid.
Time Complexity: O(N * M * 26).
Space Complexity: O(N * M).
1using System;
2using System.Collections.Generic;
3
4public class Solution {
public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList) {
var wordSet = new HashSet<string>(wordList);
var results = new List<IList<string>>();
if (!wordSet.Contains(endWord)) return results;
var queue = new Queue<IList<string>>();
queue.Enqueue(new List<string>(){beginWord});
var levelVisited = new HashSet<string>();
while (queue.Count > 0) {
int levelSize = queue.Count;
var currentLevelVisited = new HashSet<string>();
while (levelSize-- > 0) {
var currentPath = queue.Dequeue();
var lastWord = currentPath[currentPath.Count - 1];
if (lastWord.Equals(endWord)) {
results.Add(currentPath);
}
for (int i = 0; i < lastWord.Length; i++) {
char[] currentWordArr = lastWord.ToCharArray();
for (char c = 'a'; c <= 'z'; c++) {
currentWordArr[i] = c;
var newWord = new string(currentWordArr);
if (wordSet.Contains(newWord) && !levelVisited.Contains(newWord)) {
var newPath = new List<string>(currentPath);
newPath.Add(newWord);
queue.Enqueue(newPath);
currentLevelVisited.Add(newWord);
}
}
}
}
foreach (var word in currentLevelVisited) {
wordSet.Remove(word);
levelVisited.Add(word);
}
if (results.Count > 0) break;
}
return results;
}
}Implemented in C#, this solution constructs paths with queue-based BFS. The approach efficiently manages level-wise visited nodes to ensure the shortest path strategy is maintained by selectively removing words from potential transformations at each BFS level.