DDatabricks·DSASDE-2Onsite – Coding (Algorithms)
Word Ladder (Shortest Transformation)
Problem
Shortest transformation sequence length from beginWord to endWord changing one letter at a time within a word list.
Example
hit -> cog via [hot,dot,dog,lot,log,cog] -> 5
Constraints
- 1 ≤ wordList ≤ 5000
Approach
BFS over the word graph; bidirectional BFS to optimize.
added 6 days ago