DSA · Graphs / BFS · #186

Word Ladder

Module 83 · difficulty 4/5·⏱ 30:00starts on first keystroke

Given two words `beginWord` and `endWord`, and a dictionary `wordList`, return the length of the **shortest transformation sequence** from `beginWord` to `endWord`, such that: - Only one letter can be changed at a time. - Each transformed word must exist in `wordList`. The length of the sequence is the **number of words** in it (including both `beginWord` and `endWord`). Return `0` if no such sequence exists. Note: `beginWord` does **not** need to be in `wordList`, but `endWord` must be. All words have the same length and consist of lowercase letters. Implement the function `ladderLength(beginWord, endWord, wordList)`.

Examples

beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] → 5 — hit -> hot -> dot -> dog -> cog has 5 words.
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] → 0 — endWord "cog" is not in wordList, so no valid transformation exists.
beginWord = "a", endWord = "c", wordList = ["a","b","c"] → 2 — a -> c is a single-letter change; both are length 1.

Constraints

· 1 <= beginWord.length <= 10
· endWord.length == beginWord.length
· 1 <= wordList.length <= 5000
· wordList[i].length == beginWord.length
· beginWord, endWord, and wordList[i] consist of lowercase English letters
· beginWord != endWord; all words in wordList are unique

Session phases

A · Clarify

B · Approach

C · Complexity

D · Edges

E · Code

F · Tradeoff

G · Score

Phase A — Clarify

Ask questions about input bounds, types, and edge constraints.

Ask the coach clarifying questions about the problem.

When you've covered this phase, advance to the next.