102. Word Ladder
Change exactly one letter at each step to turn the beginning word into the ending word. Every word reached after a change must belong to the supplied dictionary.
Count the words in the sequence, including the endpoints. A direct transformation and a sequence with intermediate words therefore have different lengths.
Example 1
Input
hit→cog; [hot,dot,dog,lot,log,cog,cog]
Output
5
Explanation: One shortest chain is hit,hot,dot,dog,cog; duplicate cog does not create another level.
Example 2
Input
same→same; []
Output
1
Explanation: The explicitly allowed identity case needs no change or dictionary membership.
Example 3
Input
aaa→bbb; [aac,bbb]
Output
0
Explanation: The target is present but lies outside the reachable one-letter component.
Constraints
1 <= begin.length == end.length <= 200 <= dictionary.length <= 5000dictionary[i].length == begin.length- All words use lowercase English letters.
Hints
Hint 1
Treat words as vertices and one-letter changes as unit edges.
Hint 2
Generate candidates instead of comparing every word pair.
Hint 3
BFS from count one, using private-set removal to claim each dictionary word exactly once.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Discovery removes words once and counts both endpoints
"hit"
"cog"
["hot","dot","dog","lot","log","cog","cog"]
5