126. Word Ladder II
Word Ladder II (LeetCode 126) 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 Bidirectional BFS (BFS optimization for known source & target) subpattern.
How to solve Word Ladder II
Word Ladder II is a Bidirectional BFS Optimization problem, part of Graph Traversal Patterns (DFS & BFS). Optimize BFS by searching from both source and target simultaneously. Reduce time complexity significantly.
Work towards the solution in these steps:
- Consider modeling the problem as a graph traversal where each word is a node and edges exist between words that differ by one character.
- Using Breadth-First Search (BFS) can help find the shortest transformation sequences by exploring all neighbors level by level.
- To optimize, think about implementing a Bidirectional BFS starting simultaneously from both beginWord and endWord to meet in the middle and reduce search space.
The reference solution runs in O(b^(d/2)) time and O(w * l) space.
The Word Ladder II 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 "hot" -> "dot" -> "dog" -> "cog" "hit" -> "hot" -> "lot" -> "log" -> "cog"
Example 2: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: [] 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: Array, String, Backtracking, Breadth-first Search.
Reported in interviews at Uber, Amazon, Facebook, Box, Lyft, Microsoft, Google, Bloomberg.
How to practise Word Ladder II on Thita.ai
Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. 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(b^(d/2)) time and O(w * l) space.
Open Word Ladder II in the code editor, or read the Word Ladder II editorial for a worked solution with its approach and complexity analysis.
Where Word Ladder II sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Bidirectional BFS (BFS optimization for known source & target) subpattern
- The full DSA patterns sheet
Problems related to Word Ladder II
Other problems that use the same Bidirectional BFS (BFS optimization for known source & target) and Graph Traversal Patterns (DFS & BFS) techniques:
- Bus Routes — Hard, same subpattern
- Open the Lock — Medium, same subpattern
- Accounts Merge — Medium, same pattern
- Alien Dictionary — Hard, same pattern
- All Paths from Source Lead to Destination — Medium, same pattern
- Build a Matrix With Conditions — Hard, same pattern
Word Ladder II FAQ
What is the LeetCode number of Word Ladder II?
Word Ladder II is LeetCode problem 126, rated Hard.
What pattern is used to solve Word Ladder II?
Word Ladder II is a Bidirectional BFS Optimization problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Bidirectional BFS (BFS optimization for known source & target) subpattern.
What is the time complexity of Word Ladder II?
The reference solution runs in O(b^(d/2)) time and O(w * l) space.
Which companies ask Word Ladder II?
Word Ladder II has been reported in interviews at Uber, Amazon, Facebook, Box, Lyft, Microsoft, Google, Bloomberg.