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).
1#include <stdio.h>
2
This C code uses a loop-based BFS leveraging basic queue operations to explore each word's path to potential matches. A helper function ensures only one-letter transformations are pursued. The transformation check and BFS implementation are in C style for maximum control over memory and data handling.