Word Ladder II: All Shortest Transformations
Updated
Problem statement
Transform beginWord into endWord by changing exactly one character at each step. Every word after the starting word must belong to wordList. Return every transformation sequence that uses the fewest changes, including both endpoints.
For this exercise, assume all words use lowercase English letters and have the same length. Return sequences in lexicographic order: compare their words from left to right, using alphabetical word order. Return an empty array if no transformation exists. If both endpoints are equal, return the single sequence containing that word, even when the dictionary is empty.
Follow-up: how would you retain all shortest paths, avoid revisiting earlier BFS levels, and handle a large dictionary. Use BFS distances and all compatible parent links, then reconstruct the shortest sequences.
Function
findLadders(beginWord: String, endWord: String, wordList: List<String>) → List<List<String>>Examples
Example 1
beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log","cog"]return = [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]Both routes use four changes. Keep both same-depth parents of cog rather than stopping after the first route.
Example 2
beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log"]return = []The destination is absent from the dictionary, so no valid ending step exists.
Constraints
- For this exercise, assume each word has 1 through 5 letters and the dictionary contains at most 5000 distinct words.
- The starting word may appear in the dictionary. The ending word may be missing from it; then, unless it equals the starting word, no transformation exists.
- For this exercise, assume the total number of word occurrences across all returned sequences is at most 1000.
More PeopleStrong Onsite Interview questions
- Add Two Binary StringsONSITE INTERVIEW · Seen Mar 2026
- Four SumONSITE INTERVIEW · Seen Mar 2026
- LRU Cache OperationsONSITE INTERVIEW · Seen Mar 2026
- Sliding Window MaximumONSITE INTERVIEW · Seen Mar 2026
- Find the Entry of a Linked List CycleONSITE INTERVIEW · Seen Sep 2025
- Integer to English Words: Up to 20 DigitsONSITE INTERVIEW · Seen Sep 2025
- Detect a Cycle in a Linked ListONSITE INTERVIEW · Seen May 2025
- First Nonrepeating CharacterONSITE INTERVIEW · Seen May 2025
- Longest Subarray with a Target SumONSITE INTERVIEW · Seen May 2025
- Lowest Common Ancestor in a BSTONSITE INTERVIEW · Seen May 2025
Similar questions at other companies
- Word Ladder IIBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Fewest Buses with the Full RouteMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Minimum Bus Routes to a DestinationPinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Jump Game IVZomato / Eternal · ONSITE INTERVIEWZomato / Eternal interview questions
- Largest Island After One FlipOracle · ONSITE INTERVIEWOracle interview questions
- Word LadderGoogle · ONSITE INTERVIEWGoogle interview questions
- Find Duplicate Files in a FilesystemHarvey · PHONE SCREEN · ONSITE INTERVIEWHarvey interview questions
- Word LadderGoldman Sachs · PHONE SCREEN · ONSITE INTERVIEWGoldman Sachs interview questions
- Concurrent Web Crawler SimulationOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Currency Conversion RateAmazon · PHONE SCREEN · ONSITE INTERVIEW