# Word Ladder (Leetcode 127) Solution - Google Interview Question Mani
Educating everyone with the beauty of programming!!

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 <= k` is in `wordList`. Note that `beginWord` does not need to be in `wordList`.
• `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 <= 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.

Solution:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
* The logic is to preprocess the wordList in the form of *
* Eg:WordList: ["hot","dot","dog","lot","log","cog"]
* The Preprocessed output will have the following map. This is nothing but the adjacencyList for the graph.
* {do*=[dot, dog], d*g=[dog], c*g=[cog], ho*=[hot], *og=[dog, log, cog], h*t=[hot],
* lo*=[lot, log], l*t=[lot], l*g=[log],  *ot=[hot, dot, lot], d*t=[dot], co*=[cog]}
**/
class Solution {
public int ladderLength(String beginWord, String end, List<String> wordList) {
Map<String, List<String>> map = preProcess(wordList);
System.out.println(map);
//BFS from beginWord.
Set<String> visited = new HashSet<>();
Queue<String[]> q = new LinkedList<>();

Integer res = null;
while (q.size() != 0) {
String[] node = q.poll();
String cur = node;

int level = Integer.parseInt(node);

if (cur.equals(end)) {
res = level;
break;
}

if (visited.contains(cur)) {
continue;
}

for (int i = 0; i < cur.length(); i++) {
String temp = cur.substring(0, i) + "*" + cur.substring(i + 1, cur.length());
List<String> list = map.get(temp);
// System.out.println(cur + ":" + temp +  ":" + list);
if (list != null) {
for (String s : list) {
q.add(new String[]{s, (level + 1) + ""});
}
}

}

}

return res == null ? 0 : res + 1;
}

Map<String, List<String>> preProcess(List<String> words) {
Map<String, List<String>> map = new HashMap<>();
for (String w : words) {
for (int i = 0; i < w.length(); i++) {
String temp = w.substring(0, i) + "*" + w.substring(i + 1, w.length());
List<String> list = map.getOrDefault(temp, new ArrayList<>());