Word Ladder
Updated
Problem statement
You are given two words, beginWord and endWord, and a list of words wordList. All words have the same length.
A transformation sequence from beginWord to endWord is a list of words beginWord -> w1 -> w2 -> ... -> endWord where:
- each pair of neighboring words differs in exactly one letter position, and
- every word after
beginWord, includingendWord, is inwordList.beginWorditself does not need to be in the list.
Return the number of words in the shortest transformation sequence, counting both beginWord and endWord. If no such sequence exists, return 0.
Function
ladderLength(beginWord: String, endWord: String, wordList: List<String>) → intExamples
Example 1
beginWord = "cold"endWord = "warm"wordList = ["cord","card","ward","warm","worm","word","corm"]return = 5One shortest sequence is cold -> cord -> card -> ward -> warm, which has 5 words. Each step changes one letter: l to r, o to a, c to w, and d to m.
Another sequence of the same length is cold -> cord -> word -> worm -> warm. No shorter sequence exists: cold and warm differ in all 4 letters, and each step changes only one letter.
Example 2
beginWord = "cold"endWord = "warm"wordList = ["cord","card","ward","worm","word"]return = 0warm is not in wordList, so it can never be reached. The answer is 0.
Example 3
beginWord = "a"endWord = "c"wordList = ["a","b","c"]return = 2a and c differ in one letter and c is in the list, so the sequence a -> c has 2 words. Having beginWord in the list does not change anything.
Constraints
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord,endWordand everywordList[i]contain only lowercase English letters.beginWord != endWord- All words in
wordListare distinct.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- 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
- Word Ladder IIBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Shortest Word Transformation SequenceReddit · PHONE SCREENReddit interview questions
- Linked Merchants Within Two HopsStripe · PHONE SCREENStripe interview questions
- Find Minimum City HopsAmazon · OA
- Shortest Path from Encoded Graph EdgesBitGo · OABitGo interview questions
- Minimum Bus Routes to a DestinationPinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Jump Game IVZomato / Eternal · ONSITE INTERVIEWZomato / Eternal interview questions