Word Ladder
Problem Description
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 <= kis inwordList. Note thatbeginWorddoes not need to be inwordList. - 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 <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord,endWord, andwordList[i]consist of lowercase English letters.beginWord != endWord- All the words in
wordListare unique.
Solve it on LeetCode
Approaches
1. Breadth-First Search (BFS)
Intuition:
The Word Ladder problem can be thought of as a graph traversal problem where each word in the word list is a node and there is an edge between two nodes if they differ by exactly one character. The problem is then to find the shortest path from the beginWord to the endWord.
Breadth-First Search (BFS) is a perfect fit for this type of problem because it explores all nodes at the present "depth" level before moving on to nodes at the next depth level, thereby ensuring that we find the shortest path.
Code:
- Time Complexity: O(N * M * 26) where N is the number of words in the word list and M is the length of each word. For every word, in the worst case, we change each character (M) to every other character in the alphabet (26 possibilities).
- Space Complexity: O(N * M) for the wordSet and queue data structures.
2. Bidirectional BFS
Intuition:
Bidirectional BFS is an optimization of the traditional BFS technique. Instead of searching from one end to the other, we simultaneously search from both the beginWord and the endWord towards each other. The search halts when the two searches meet. This significantly reduces the search space and can greatly increase efficiency, especially as the length of transformation increases.
Code:
- Time Complexity: O(N * M * 26) similar to BFS. However, in practice, the performance can be significantly better since we are working on possibly halved problem size.
- Space Complexity: O(N * M) for the word sets and additional data structures. However, it tends to require less space on average compared to the unidirectional BFS.