Given two words (beginWord and endWord), and a dictionary of word list, find the length of the shortest transformation sequence from `beginWord` to `endWord`, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume `beginWord` and `endWord` are non-empty and are not the same.

Example 1:

```Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5
Explanation: As one shortest transformation is "hit"-> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.```

Example 2:

```Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.```

We are given a `beginWord` and an `endWord`. Let these two represent `start node` and `end node` of a graph. We have to reach from the start node to the end node using some intermediate nodes/words. The intermediate nodes are determined by the given `wordList` to us. The only condition for every step we take on this ladder of words is the current word should change by just `one letter`. We will essentially be working with an undirected and unweighted graph with words as nodes and edges between words which differ by just one letter. The problem boils down to finding the shortest path from a start node to a destination node if there exists one. Hence it can be solved using `Breadth First Search` approach.

Intuition

Start from `beginWord` and search the `endWord` using BFS.

Algorithm

1. Do the pre-processing on the given `wordList` and create a lookup friendly dictionary from it. An obvious choice is a `HashSet`
2. Push the `beginWord` in the `queue` and initialize `len `by 1.
3. While the `queue `has elements, get the front element of the queue. Let’s call this word as `curWord`.
4. Find all the generic transformations of the `curWord` and find out if any of these transformations is also a transformation of other words in the word list. This is achieved by checking if the transformed word is present in the `HashSet`.
5. If a transformed word is found in the dictionary(`HashSet)`, then create a new word from it add the same to `Queue`
6. After we finishes the lookup for all the words in current level increment the counter `len` by 1.
7. Eventually, if you reach the desired word, the current len is the shortest transformation sequence length.
```class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {

Set<String> dict = new HashSet<>(wordList);
queue.offer(beginWord);
int len = 1;

while(!queue.isEmpty()){
int size = queue.size();
for(int k = 0 ; k < size ; k++){
String curWord = queue.poll();
if(endWord.equals(curWord)){
return len;
}
char[] arr = curWord.toCharArray();
for(int i = 0 ; i < arr.length ; i++){
char temp = arr[i];
for(char a = 'a' ; a <= 'z' ; a++){
arr[i] = a;
String newWord = String.valueOf(arr);
if(dict.contains(newWord)){
dict.remove(newWord);
}
}
arr[i] = temp;
}
}
len++;
}
return 0;
}
}
```

The time complexity is `O(N*M)`, where `N` is the size of the dictionary and `M` is the length of the word.

Details:

• To generate all neighbors – `O(26 * M).`
• To check if the word exists in the dictionary – `O(1)`. This is a reason why it is better to put all words to the `HashSet`.
• To generate a `Queue` and traverse the `Queue` via BFS`O(N)`

Categories: BFS