2dbi
Home/Google/Word Ladder — Shortest Transformation Sequence Length
GGoogle·DSAL4Onsite – Coding 2

Word Ladder — Shortest Transformation Sequence Length

Problem

Given a beginWord, endWord, and a wordList, return the length of the shortest transformation sequence from beginWord to endWord where each step changes exactly one letter and each intermediate word must be in wordList.

Return 0 if no such sequence exists.

Example

beginWord = "hit", endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5  -- hit → hot → dot → dog → cog

Constraints

  • 1 ≤ wordList.length ≤ 5000
  • All words have the same length

Follow-up (Word Ladder II)

Return all shortest transformation sequences. This is significantly harder — BFS + backtracking.

added 6 days ago
LeadersAccount