🧠
Brute Force (Check All Possible Transformations via DFS)
💡 This approach tries all possible transformations recursively without pruning or optimization. It helps understand the problem's exponential nature and why BFS is better for shortest path.
Intuition
Try every possible one-letter change at each step and recursively search for the endWord. This explores all paths but is very slow.
Algorithm
- Start from beginWord.
- At each step, generate all words differing by one letter that are in wordList and not visited.
- Recursively search from each generated word to find endWord.
- Return the minimum path length found or 0 if none.
💡 The recursion tree grows exponentially because each word can lead to many others, making it hard to track and inefficient.
def word_ladder_bruteforce(beginWord, endWord, wordList):
word_set = set(wordList)
min_steps = [float('inf')]
visited = set()
def dfs(current_word, steps):
if current_word == endWord:
min_steps[0] = min(min_steps[0], steps)
return
for i in range(len(current_word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
if c == current_word[i]:
continue
next_word = current_word[:i] + c + current_word[i+1:]
if next_word in word_set and next_word not in visited:
visited.add(next_word)
dfs(next_word, steps + 1)
visited.remove(next_word)
visited.add(beginWord)
dfs(beginWord, 1)
return min_steps[0] if min_steps[0] != float('inf') else 0
# Example usage:
if __name__ == '__main__':
begin = "hit"
end = "cog"
word_list = ["hot","dot","dog","lot","log","cog"]
print(word_ladder_bruteforce(begin, end, word_list) )
Line Notes
word_set = set(wordList)Convert list to set for O(1) membership checks
min_steps = [float('inf')]Use list to allow modification inside nested dfs function
visited = set()Track visited words to avoid cycles
def dfs(current_word, steps):Recursive DFS exploring all transformation paths
if current_word == endWord:Base case: found target, update minimum steps
for i in range(len(current_word))Try changing each character position
for c in 'abcdefghijklmnopqrstuvwxyz'Try all possible letters for replacement
if next_word in word_set and next_word not in visitedOnly proceed if next_word is valid and unvisited
visited.add(next_word)Mark next_word as visited to avoid cycles
dfs(next_word, steps + 1)Recurse deeper with incremented step count
visited.remove(next_word)Backtrack to explore other paths
visited.add(beginWord)Start with beginWord marked visited
dfs(beginWord, 1)Begin DFS with step count 1
return min_steps[0] if min_steps[0] != float('inf') else 0Return minimum steps found or 0 if none
import java.util.*;
public class WordLadderBruteForce {
public static int wordLadder(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
int minSteps = Integer.MAX_VALUE;
Set<String> visited = new HashSet<>();
visited.add(beginWord);
minSteps = dfs(beginWord, endWord, wordSet, visited, 1, minSteps);
return minSteps == Integer.MAX_VALUE ? 0 : minSteps;
}
private static int dfs(String current, String endWord, Set<String> wordSet, Set<String> visited, int steps, int minSteps) {
if (current.equals(endWord)) {
return Math.min(minSteps, steps);
}
char[] arr = current.toCharArray();
for (int i = 0; i < arr.length; i++) {
char original = arr[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original) continue;
arr[i] = c;
String nextWord = new String(arr);
if (wordSet.contains(nextWord) && !visited.contains(nextWord)) {
visited.add(nextWord);
minSteps = dfs(nextWord, endWord, wordSet, visited, steps + 1, minSteps);
visited.remove(nextWord);
}
}
arr[i] = original;
}
return minSteps;
}
public static void main(String[] args) {
List<String> wordList = Arrays.asList("hot","dot","dog","lot","log","cog");
System.out.println(wordLadder("hit", "cog", wordList));
}
}
Line Notes
Set<String> wordSet = new HashSet<>(wordList);HashSet for O(1) lookups
int minSteps = Integer.MAX_VALUE;Initialize minSteps to max value before DFS
Set<String> visited = new HashSet<>();Track visited words to avoid cycles
visited.add(beginWord);Mark beginWord visited before DFS
minSteps = dfs(beginWord, endWord, wordSet, visited, 1, minSteps);Start DFS with step count 1 and minSteps
private static int dfs(...)Recursive DFS returning minimum steps found
if (current.equals(endWord)) {Base case: found target word
for (int i = 0; i < arr.length; i++) {Try changing each character
for (char c = 'a'; c <= 'z'; c++) {Try all letters a-z
if (wordSet.contains(nextWord) && !visited.contains(nextWord)) {Proceed only if valid and unvisited
visited.add(nextWord);Mark nextWord visited before recursion
minSteps = dfs(...);Update minSteps with recursive result
visited.remove(nextWord);Backtrack after recursion
#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
#include <climits>
using namespace std;
int dfs(string current, const string& endWord, unordered_set<string>& wordSet, unordered_set<string>& visited, int steps, int minSteps) {
if (current == endWord) {
return min(minSteps, steps);
}
for (int i = 0; i < (int)current.size(); i++) {
char original = current[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original) continue;
current[i] = c;
if (wordSet.count(current) && !visited.count(current)) {
visited.insert(current);
minSteps = dfs(current, endWord, wordSet, visited, steps + 1, minSteps);
visited.erase(current);
}
}
current[i] = original;
}
return minSteps;
}
int wordLadderBruteForce(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
unordered_set<string> visited;
visited.insert(beginWord);
int minSteps = INT_MAX;
minSteps = dfs(beginWord, endWord, wordSet, visited, 1, minSteps);
return minSteps == INT_MAX ? 0 : minSteps;
}
int main() {
vector<string> wordList = {"hot","dot","dog","lot","log","cog"};
cout << wordLadderBruteForce("hit", "cog", wordList) << endl;
return 0;
}
Line Notes
#include <iostream>Include for input/output
#include <vector>Include for vector container
#include <unordered_set>Include for hash set
#include <string>Include for string operations
#include <climits>Include for INT_MAX
int dfs(...)Recursive DFS returning minimum steps found
if (current == endWord) {Base case: found target word
for (int i = 0; i < (int)current.size(); i++) {Try changing each character
for (char c = 'a'; c <= 'z'; c++) {Try all letters a-z
if (wordSet.count(current) && !visited.count(current)) {Proceed only if valid and unvisited
visited.insert(current);Mark current word visited before recursion
minSteps = dfs(...);Start DFS with step count 1
visited.erase(current);Backtrack after recursion
int wordLadderBruteForce(...)Main function to initiate DFS
unordered_set<string> wordSet(wordList.begin(), wordList.end());Fast membership checks
unordered_set<string> visited;Track visited words
visited.insert(beginWord);Mark beginWord visited
int minSteps = INT_MAX;Initialize minSteps
return minSteps == INT_MAX ? 0 : minSteps;Return minimum steps or 0 if none
int main()Main function to test code
cout << ...Print result
return 0;Exit program
function wordLadderBruteForce(beginWord, endWord, wordList) {
const wordSet = new Set(wordList);
let minSteps = Infinity;
const visited = new Set();
function dfs(currentWord, steps) {
if (currentWord === endWord) {
minSteps = Math.min(minSteps, steps);
return;
}
for (let i = 0; i < currentWord.length; i++) {
for (let c = 97; c <= 122; c++) { // 'a' to 'z'
const char = String.fromCharCode(c);
if (char === currentWord[i]) continue;
const nextWord = currentWord.slice(0, i) + char + currentWord.slice(i + 1);
if (wordSet.has(nextWord) && !visited.has(nextWord)) {
visited.add(nextWord);
dfs(nextWord, steps + 1);
visited.delete(nextWord);
}
}
}
}
visited.add(beginWord);
dfs(beginWord, 1);
return minSteps === Infinity ? 0 : minSteps;
}
// Example usage:
console.log(wordLadderBruteForce("hit", "cog", ["hot","dot","dog","lot","log","cog"]));
Line Notes
const wordSet = new Set(wordList);Use Set for O(1) lookups
let minSteps = Infinity;Track minimum steps found
const visited = new Set();Track visited words to avoid cycles
function dfs(currentWord, steps) {Recursive DFS exploring all paths
if (currentWord === endWord) {Base case: found target word
for (let i = 0; i < currentWord.length; i++) {Try changing each character
for (let c = 97; c <= 122; c++) {Try all letters a-z using char codes
const char = String.fromCharCode(c);Convert char code to character
if (char === currentWord[i]) continue;Skip if same character
const nextWord = currentWord.slice(0, i) + char + currentWord.slice(i + 1);Generate next word
if (wordSet.has(nextWord) && !visited.has(nextWord)) {Proceed only if valid and unvisited
visited.add(nextWord);Mark nextWord visited before recursion
dfs(nextWord, steps + 1);Recurse deeper with incremented step count
visited.delete(nextWord);Backtrack after recursion
visited.add(beginWord);Start with beginWord marked visited
dfs(beginWord, 1);Begin DFS with step count 1
return minSteps === Infinity ? 0 : minSteps;Return minimum steps found or 0 if none
TimeO(N * 26^L * L) where N is wordList size and L is word length
SpaceO(N * L) for recursion stack and visited set
At each step, we try changing each character (L positions) to 26 letters, and recurse for each valid word. This leads to exponential growth.
💡 For word length 3 and 1000 words, this approach can try millions of paths, making it impractical.
Interview Verdict: TLE
This approach is too slow for large inputs but is useful to understand the problem's complexity and why BFS is needed.
