Word Ladder

Hard · Graphs

You are given a start word, a target word, and a list of allowed words, all of the same fixed length made of lowercase letters. Starting from the start word, you may transform it step by step into a new word by changing exactly one letter at a time, and every intermediate word you produce (except the very first) must appear in the allowed list. Return the total number of words in the shortest such chain from the start word to the target word, inclusive of both endpoints. If no such chain exists, return 0.

Examples

Input:  beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Why:    One shortest chain is hit -> hot -> dot -> dog -> cog, changing one letter each step, giving 5 words total.

Input:  beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Why:    The target word cog never appears in the allowed word list, so no chain can reach it.

Input:  beginWord = "a", endWord = "c", wordList = ["a","b","c"]
Output: 2
Why:    Changing the single letter directly from a to c forms a valid two-word chain.

Constraints

1 <= beginWord.length <= 10, endWord.length == beginWord.length, 1 <= wordList.length <= 5000, all words consist of lowercase English letters and have the same length, beginWord != endWord, all words in wordList are distinct

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Word Ladder

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Word Ladder. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.