126. Word Ladder II
Approach
BFS to find the shortest path length and build word adjacency levels,
then DFS backtracking to reconstruct all shortest transformation sequences.
Key Techniques
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Backtracking explores all possible solutions by building candidates incrementally and abandoning ("pruning") branches that cannot lead to a valid result. It powers N-Queens, Sudoku solver, permutations, and subset generation. Prune early to reduce the effective search space.
// Approach: BFS to find the shortest path length and build word adjacency levels,
// then DFS backtracking to reconstruct all shortest transformation sequences.
// Time: O(n·w²) Space: O(n·w)
public class Solution
{
Dictionary<string, int> mpp;
IList<IList<string>> ans;
string b;
private void WLDFS(string word, List<string> seq)
{
if (word.Equals(b))
{
var dup = new List<string>(seq);
dup.Reverse();
ans.Add(dup);
return;
}
int steps = mpp[word];
int n = word.Length;
for (int i = 0; i < n; i++)
{
for (char ch = 'a'; ch <= 'z'; ch++)
{
char[] replacedCharArray = word.ToCharArray();
replacedCharArray[i] = ch;
string newWord = new string(replacedCharArray);
if (mpp.ContainsKey(newWord) && mpp[newWord] + 1 == steps)
{
seq.Add(newWord);
WLDFS(newWord, seq);
seq.RemoveAt(seq.Count - 1);
}
}
}
}
public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList)
{
HashSet<string> set = new HashSet<string>();
foreach (string word in wordList)
{
set.Add(word);
}
Queue<string> q = new Queue<string>();
b = beginWord;
q.Enqueue(beginWord);
mpp = new Dictionary<string, int>();
mpp.Add(beginWord, 1);
int n = beginWord.Length;
set.Remove(beginWord);
while (q.Count > 0)
{
string word = q.Dequeue();
int steps = mpp[word];
if (word.Equals(endWord))
break;
for (int i = 0; i < n; i++)
{
for (char ch = 'a'; ch <= 'z'; ch++)
{
char[] replacedCharArray = word.ToCharArray();
replacedCharArray[i] = ch;
string newWord = new string(replacedCharArray);
if (set.Contains(newWord))
{
q.Enqueue(newWord);
set.Remove(newWord);
if (!mpp.ContainsKey(newWord))
mpp.Add(newWord, steps + 1);
else
mpp[newWord] = steps + 1;
}
}
}
}
ans = new List<IList<string>>();
if (mpp.ContainsKey(endWord))
{
List<string> seq = new List<string>();
seq.Add(endWord);
WLDFS(endWord, seq);
}
return ans;
}
}