2dbi
Home/Databricks/Word Ladder (Shortest Transformation)
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
LeadersAccount