# Word Ladder - Length of Shortest Transformation to Reach a Target Word

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> $s_1$ -> $s_2$ -> … -> $s_k$ such that:

• Every adjacent pair of words differs by a single letter.
• Every $s_i$ for $1 <= i <= k$ is in wordList. Note that beginWord does not need to be in wordList.
• $s_k$ == 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.

### Idea

The solution to this problem is similar to this one: Open the Lock.

Since only one character can be changed a time, we can change the characters one at a time and check if it exists in the wordList. Then, we can assume the word as a neighbor to the previous word.

For the first example - [“hot”,“dot”,“dog”,“lot”,“log”,“cog”], neighbors of “hot” is ”dot” and ”lot”.

Now, we can run a BFS starting from the beginWord and the level where endWord exists, is the length of the shortest transformation sequence.

### Implementation

In C++:

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> words (wordList.begin(), wordList.end());
// if endWord doesn't exist, return 0
if (!words.count(endWord)) return 0;
unordered_set<string> visited;
queue<string> q;
q.push(beginWord);
visited.insert(beginWord);
int level = 1;
while(!q.empty()) {
int size = q.size();
while(size--) {
string s = q.front();
q.pop();
// iterate over all the characters of s
for (int i = 0; i < (int)s.length(); ++i) {
string changed = s;
// change the characters from 'a' to 'z'
for (char c = 'a'; c <= 'z'; ++c) {
if (c == s[i]) continue;
changed[i] = c;
// pre-emptively check
if (changed == endWord) {
return 1 + level;
}
if (!visited.count(changed) and words.count(changed)) {
q.push(changed);
visited.insert(changed);
}

}
}
}
++level;
}
return 0;
}

### Complexity Analysis

• Time Complexity: $O(N * M * M * 26) = O(NM^2)$ where $N =$ length of wordList and $M =$ average length of the strings. Look-up time for wordList hashset is $O(M)$.
• Space Complexity: $O(N * M)$.

### Idea

Since the start node and the target node are fixed, we can run bidirectional BFS (from both start and end) to improve the time complexity from $O(b^d)$ to $O(b^{d/2})$ (where $b =$ branching factor of the tree and $d =$ distance of target from source).

### Implementation

In C++:

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> begin({beginWord}),
end({endWord}),
words(wordList.begin(), wordList.end());
// if endWord doesn't exist, thus return 0
if(!words.count(endWord)) return 0;
int level = 1;
unordered_set<string> visited;
while(begin.size() and end.size()) {
unordered_set<string> next;
// always consider the smaller set first
if (begin.size() > end.size()) {
swap(begin, end);
}
for (string s: begin) {
for (int i = 0; i < (int)s.length(); ++i) {
string changed = s;
for (char c = 'a'; c <= 'z'; ++c) {
if (c == s[i]) continue;
changed[i] = c;
// pre-emptively check
if (end.count(changed)) {
return 1 + level;
}
if (!visited.count(changed) and words.count(changed)) {
next.insert(changed);
visited.insert(changed);
}

}
}
}
++level;
// we have moved to the next level
begin = next;
}
return 0;
}

### Complexity Analysis

• Time Complexity: $O(b^{d/2} + b^{d/2}) = O(b^{d/2})$, where $b =$ branching factor of the tree and $d =$ distance of target from source.
• Space Complexity: $O((N + N) * M) = O(N * M)$ (where $N =$ size of wordList), required for begin, end, and visited hashsets.