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).
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.