Word Ladder II (All Shortest Paths)

HardGraphsbfs + backtracking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given two words, beginWord and endWord, and a dictionary wordList. A **transformation sequence** from beginWord to endWord is a list of words s1, s2, ..., sk such that: - s1 == beginWord and sk == endWord. - Every adjacent pair of words differs in exactly **one** letter (the words are all the same length). - Each si for 2 <= i <= k is present in wordList. Note that beginWord itself does **not** need to be in wordList. Return **all** the shortest transformation sequences from beginWord to endWord, where each sequence is returned as the list of words [beginWord, s2, ..., endWord]. If no such sequence exists, return an empty list. You may return the sequences in any order, and the sequences within the answer may be ordered arbitrarily. A naive approach that explores every path will time out: you must find the shortest distance first (typically with BFS) and then reconstruct only the paths that achieve that shortest distance (typically with backtracking over a parent/predecessor structure).

Examples

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
There are two shortest transformation sequences, both of length 5. Each step changes exactly one letter and every intermediate word is in the dictionary.
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
The endWord "cog" is not in wordList, so no valid transformation sequence can end at it. The answer is empty.
Input: beginWord = "red", endWord = "tax", wordList = ["ted","tex","red","tax","tad","den","rex","pee"]
Output: [["red","ted","tad","tax"],["red","ted","tex","tax"],["red","rex","tex","tax"]]
All three sequences have the minimum length of 4, so all are returned.

Constraints

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 500
  • wordList[i].length == beginWord.length
  • beginWord, endWord, and every wordList[i] consist of lowercase English letters
  • beginWord != endWord
  • All words in wordList are unique

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.