Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

153. Word Ladder

HardDay 45 of 60Graphs

You are given two words beginWord and endWord of the same length and a dictionary wordList. In one step you may change exactly one letter, and every intermediate word (and endWord) must be in wordList. Return the number of words in the shortest transformation sequence from beginWord to endWord, counting both ends, or 0 if no sequence exists.

Example 1
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
"hit" to "hot" to "dot" to "dog" to "cog" has 5 words.
Example 2
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
"cog" is not in the list, so it can never be reached.
Constraints
  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • All words are lowercase English letters
  • beginWord != endWord
  • Words in wordList are unique
Hints
Frequently asked at: Amazon, Meta, Google, LinkedIn
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min