Sponsored
Sponsored
This approach leverages Breadth First Search (BFS), where each word is a node in the graph, and an edge exists between two nodes if they differ by exactly one letter. The goal is to find the shortest path from beginWord to endWord.
Start BFS from the beginWord, exploring transformations by changing each letter and checking if the new word exists in the set of available words. Polished implementation should consider preprocessing the word list for efficient lookup.
Time Complexity: O(N * m^2), where N is the number of words in the list and m is the length of each word. Each word pair is compared in the worst case.
Space Complexity: O(N), where N is the number of nodes (words) we store in the queue.
1import java.util.*;
2
3public class WordLadder {
4 public int ladderLength(String beginWord, String endWord, List<String> wordList) {
5 Set<String> wordSet = new HashSet<>(wordList);
6 if (!wordSet.contains(endWord)) return 0;
7 Queue<String> q = new LinkedList<>();
8 q.add(beginWord);
9 int ladder = 1;
10
11 while (!q.isEmpty()) {
12 int levelSize = q.size();
13 for (int i = 0; i < levelSize; i++) {
14 String current = q.poll();
15 for (int j = 0; j < current.length(); j++) {
16 char[] currArray = current.toCharArray();
17 for (char c = 'a'; c <= 'z'; c++) {
18 currArray[j] = c;
19 String temp = new String(currArray);
20 if (temp.equals(endWord)) return ladder + 1;
21 if (wordSet.contains(temp)) {
22 q.add(temp);
23 wordSet.remove(temp);
24 }
25 }
26 }
27 }
28 ladder++;
29 }
30 return 0;
31 }
32
33 public static void main(String[] args) {
34 WordLadder wl = new WordLadder();
35 List<String> wordList = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");
36 System.out.println(wl.ladderLength("hit", "cog", wordList));
37 }
38}In this Java implementation, transformations are checked by swapping each character of the current word with every letter from 'a' to 'z'. If the transformed word matches endWord, the method returns the current ladder depth plus one. A discovered valid transformation means deleting it from the set to avoid redundant processing.