Word Ladder

Hard· BFS· Shortest Path

Problem

Given a start word, an end word and a dictionary, you may change one letter at a time, and every intermediate word must be in the dictionary. Return the number of words in the shortest such sequence from start to end, or 0 if none exists.

Examples

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

Output: 5

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

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

Output: 0

The end word is not in the dictionary.

Constraints

• 1 <= beginWord.length <= 10
• 1 <= wordList.length <= 5000
• All words are lowercase and the same length

Hints & approach

Hint 1

Words are nodes; two words are adjacent when they differ in exactly one position.

Hint 2

Shortest sequence in an unweighted graph means BFS.

Hint 3

Generate neighbours by trying all 26 letters in each position and checking the dictionary set.

Approachtry the hints first

Put the dictionary in a hash set and return 0 if the end word is missing. BFS from the start word, tracking the level. For each word, try replacing every position with every letter; any candidate in the set that is unvisited is enqueued (and removed from the set to mark it visited). Return the level when the end word is dequeued. Bidirectional BFS from both ends can cut the search space further.

Time O(N * L * 26) · Space O(N * L)

← PreviousMin Cost to Connect All Points Next →Swim in Rising Water