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.
1from collections import defaultdict, deque
2
3def findLadders(beginWord, endWord, wordList):
4 def construct_paths(source, destination, tree):
5 if source == destination:
6 return [[source]]
7 return [[source] + path for succ in tree[source] for path in construct_paths(succ, destination, tree)]
8
9 if endWord not in wordList or not endWord or not beginWord or not wordList:
10 return []
11 tree, words, n = defaultdict(set), set(wordList), len(beginWord)
12 found, q, nq = False, {beginWord}, set()
13 while q and not found:
14 words -= q
15 for x in q:
16 for y in ([x[:i] + chr(c) + x[i+1:] for c in range(ord('a'), ord('z')+1)] for i in range(n)):
17 for z in y:
18 if z in words:
19 if z == endWord:
20 found = True
21 else:
22 nq.add(z)
23 tree[x].add(z)
24 q, nq = nq, set()
25 return construct_paths(beginWord, endWord, tree)This Python code uses a bidirectional approach to construct all possible paths from the beginning to the end word. The set operations ensure efficient word lookups and deletions, while the recursive helper function constructs all paths once the tree is established.
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.