Word Ladder

hardFREETrees & GraphsGoogle DSA

Given two words beginWord and endWord, and a word list, return the number of words in 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 the word list.

Return 0 if no such transformation sequence exists. Note that beginWord does not need to be in the word list.

Example

Input

hit
cog
hot,dot,dog,lot,log,cog

Output

Reasoning

The transformation sequence starts with the beginWord "hit" and explores neighboring words by changing one letter at a time.
The sequence proceeds as follows: "hit" $\rightarrow$ "hot" $\rightarrow$ "dot" $\rightarrow$ "dog" $\rightarrow$ "cog", with each word being in the given word list.
This sequence has a length of $5$ , which is the shortest possible transformation sequence from "hit" to "cog".
Since no shorter sequence exists, the output is $5$ , representing the number of words in this shortest transformation sequence.

Constraints

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= len(wordList) <= 5000
All words have the same length
Words consist of lowercase English letters

Learn this in

GraphsDSA Study Plan

More from Google DSA

Time Based Key-Value Storemedium Moving Average from Data Streameasy Snapshot Arraymedium LRU Cachemedium Find Peak Elementeasy

Concept primer

Background Knowledge

The Word Ladder problem is a classic example of a graph theory problem, specifically involving unweighted graphs and shortest paths. In this context, each word in the word list represents a node (or vertex) in the graph, and two nodes are connected by an edge if the corresponding words differ by only one letter. This type of graph is often referred to as a word graph. The goal is to find the shortest path between the beginWord node and the endWord node, where each step in the path represents a single-letter transformation.

To understand this problem, it's essential to be familiar with graph traversal algorithms, such as Breadth-First Search (BFS) and Depth-First Search (DFS). BFS is particularly well-suited for finding shortest paths in unweighted graphs, as it explores all nodes at a given distance from the starting node before moving on to the next distance level. Additionally, the concept of neighborhood is crucial, as it refers to the set of nodes that are directly connected to a given node. In the context of the Word Ladder problem, the neighborhood of a word consists of all words that can be obtained by changing one letter.

The Word Ladder problem also involves string manipulation and pattern matching, as we need to generate all possible words that differ from a given word by only one letter. This can be achieved by iterating over each character in the word and replacing it with all possible letters (e.g., 'a' to 'z'). The resulting words can then be checked against the word list to determine if they exist and can be added to the graph.

Algorithm/Approach

The general approach to solving the Word Ladder problem involves using a Breadth-First Search (BFS) algorithm to traverse the word graph and find the shortest path between the beginWord and endWord nodes. The algorithm can be summarized as follows:

Create a graph where each word in the word list is a node, and two nodes are connected if the corresponding words differ by only one letter.
Use BFS to traverse the graph, starting from the beginWord node.
At each step, generate all possible words that differ from the current word by only one letter and check if they exist in the word list.
If a word is found to exist, add it to the graph and mark it as visited to avoid revisiting it later.

Step-by-Step Strategy

To implement the solution, follow these steps:

Create a word list data structure (e.g., a set or dictionary) to store the given words.
Initialize a queue data structure to store the nodes to be visited, starting with the beginWord node.
Create a visited set to keep track of the nodes that have already been visited.
While the queue is not empty, dequeue a node and generate all possible words that differ from it by only one letter.
For each generated word, check if it exists in the word list and if it has not been visited before.
If the word exists and has not been visited, mark it as visited and add it to the queue.
If the endWord node is found, return the distance (i.e., the number of steps) from the beginWord node to the endWord node.
If the queue is empty and the endWord node has not been found, return 0 to indicate that no transformation sequence exists.

Common Pitfalls

When implementing the solution, watch out for the following common pitfalls:

Failing to check if a generated word exists in the word list before adding it to the queue.
Not marking visited nodes to avoid revisiting them later.
Not handling the case where the beginWord or endWord is not in the word list.
Using a Depth-First Search (DFS) algorithm instead of Breadth-First Search (BFS), which can lead to incorrect results.

Time & Space Complexity

The expected time complexity of the solution is $O(N \cdot M \cdot 26)$ , where $N$ is the number of words in the word list, $M$ is the length of each word, and $26$ is the number of possible letters in the alphabet. The space complexity is $O(N)$ , as we need to store the word list and the visited nodes. Note that the time complexity can be optimized by using a more efficient data structure, such as a trie, to store the word list.

solution.py

Python 3.13

Test results