127. Word Ladder
Word Ladder (LeetCode 127) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Connected Components / Island Counting subpattern.
How to solve Word Ladder
Word Ladder is a BFS Connected Components problem, part of Graph Traversal Patterns (DFS & BFS). Use BFS for shortest path in unweighted graphs. Solve word ladder, rotting oranges, and matrix problems.
Work towards the solution in these steps:
- Think of the problem as finding the shortest path in a graph where each node represents a word, and edges connect words that differ by exactly one letter.
- To efficiently find neighbors for each word, consider how you can transform words by changing one letter at a time and check if the new word exists in the dictionary.
- Breadth-first search (BFS) is well-suited here because it explores all words at the current transformation depth before moving deeper, ensuring the shortest path is found.
The reference solution runs in O(N * L^2) time and O(N * L) space.
The Word Ladder solution and editorial walks through the full approach with reference code.
Problem statement
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
- Every adjacent pair of words differs by a single letter.
- Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
- sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
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 the words in wordList are unique.
Topics and companies
Topics: Hash Table, String, Breadth-First Search.
Reported in interviews at Amazon, Facebook, Lyft, Microsoft, Google, Uber, Bloomberg, Qualtrics, Snapchat, Oracle, Yahoo, Apple and others.
How to practise Word Ladder on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N * L^2) time and O(N * L) space.
Open Word Ladder in the code editor, or read the Word Ladder editorial for a worked solution with its approach and complexity analysis.
Where Word Ladder sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Graph BFS - Connected Components / Island Counting subpattern
- The full DSA patterns sheet
Problems related to Word Ladder
Other problems that use the same Graph BFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:
- 01 Matrix — Medium, same subpattern
- Rotting Oranges — Medium, same subpattern
- Shortest Path in Binary Matrix — Medium, same subpattern
- Walls and Gates — Medium, same subpattern
- Accounts Merge — Medium, same pattern
- Alien Dictionary — Hard, same pattern
Word Ladder FAQ
What is the LeetCode number of Word Ladder?
Word Ladder is LeetCode problem 127, rated Hard.
What pattern is used to solve Word Ladder?
Word Ladder is a BFS Connected Components problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Connected Components / Island Counting subpattern.
What is the time complexity of Word Ladder?
The reference solution runs in O(N * L^2) time and O(N * L) space.
Which companies ask Word Ladder?
Word Ladder has been reported in interviews at Amazon, Facebook, Lyft, Microsoft, Google, Uber, Bloomberg, Qualtrics, Snapchat, Oracle, Yahoo, Apple and others.