Word Ladder

Given a begin word, an end word, and a dictionary, return the length of the shortest transformation sequence where each step changes exactly one letter and every intermediate word must be in the dictionary. Pattern focus: Unweighted BFS distance. Each word is a node and each valid one-letter change is an edge.

Input Format

beginWord = start word, endWord = target word, wordList = allowed dictionary

Output Format

length of the shortest transformation sequence, or 0 if impossible

Constraints

  • 1 <= wordList.length <= 5000
  • All words have the same length and contain only lowercase English letters.

Examples

Example 1:

Input:

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

Output:

5

Explanation:

hit -> hot -> dot -> dog -> cog uses five words.

Example 2:

Input:

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output:

0

Explanation:

The end word is not in the dictionary.

Example 3:

Input:

beginWord = "a"
endWord = "c"
wordList = ["a","b","c"]

Output:

2

Explanation:

A one-step transformation reaches the target.

Loading...
Word Ladder - Shortest Path DSA Problem