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.
1using System;
2using System.Collections.Generic;
3
4class WordLadder {
5 public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
6 HashSet<string> wordSet = new HashSet<string>(wordList);
7 if (!wordSet.Contains(endWord)) return 0;
8 Queue<string> q = new Queue<string>();
9 q.Enqueue(beginWord);
10 int ladder = 1;
11
12 while (q.Count > 0) {
13 int levelSize = q.Count;
14 for (int i = 0; i < levelSize; i++) {
15 string current = q.Dequeue();
16 char[] currArray = current.ToCharArray();
17 for (int j = 0; j < currArray.Length; j++) {
18 for (char c = 'a'; c <= 'z'; c++) {
19 currArray[j] = c;
20 string newWord = new string(currArray);
21 if (newWord.Equals(endWord)) return ladder + 1;
22 if (wordSet.Contains(newWord)) {
23 q.Enqueue(newWord);
24 wordSet.Remove(newWord);
25 }
26 }
27 currArray[j] = current[j];
28 }
29 }
30 ladder++;
31 }
32 return 0;
33 }
34
35 static void Main(string[] args) {
36 List<string> wordList = new List<string>() { "hot", "dot", "dog", "lot", "log", "cog" };
37 WordLadder wl = new WordLadder();
38 Console.WriteLine(wl.LadderLength("hit", "cog", wordList));
39 }
40}In this C# solution, BFS is used to find the shortest path by exploring all possible one-letter transformations at each level. Hash set ensures quick membership checks, while queue assists in breadth exploration. Upon hitting endWord, the current path depth is incremented and returned.