Word Ladder | HashMap + BFS

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

1. Every adjacent pair of words differs by a single letter.
2. Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
3. sk == endWord

Given two words, 

1. beginWord and endWord,
2. and a dictionary wordList,
3. 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.

1. Take the endWord if not in the array return 0 || -1
2. For each word in the array, we build a pattern
3. for hot , *ot, h*t, ho*
4. beginWord should exist to start finding the path
5. create a map starting from beginWord and it's subsequent pattern
6. once we build this pattern for each word, then we can start traversal algorithm from itself i.e beginWord, 1 level
7. start a bfs traversal from this begin word

while(0 < queue.length){

1. const [currentWord, length]
2. take the currentWord and length
3. find all the patterns of the currentWord
4. for each pattern we then get the neighbours from the pattern
5. .iterate over the neighbour of neighbours
6. if neighbour is word we are seawrching then return level + 1
7. else add the neighbour along with level + 1 back into the queue.
8. also keep track of the seen words or neigbour by utlizing the set.

}

let map = {}
if (!wordList.includes(endWord)) return 0
if (!wordList.includes(beginWord)) {
    wordList.push(beginWord)
}

for (let word of wordList) {
    for (let i = 0; i < word.length; i++) {
        let pattern = word.substring(0, i) + '*' + word.substring(i + 1)
        if (!map[pattern]) map[pattern] = []
        map[pattern].push(word)
    }
}

let queue = []
queue.push([beginWord, 1])
let result = 0
const seen = new Set()

while (0 < queue.length) {
    const [currentWord, level] = queue.shift()
    for (let i = 0; i < currentWord.length; i++) {
        let pattern = currentWord.substring(0, i) + '*' + currentWord.substring(i + 1)
        // *ot, h*t, ho*
        // for each pattern i will find form th map

        let neighbours = map[pattern] || []

        for (let neighbour of neighbours) {
            if (neighbour === endWord) {
                return level + 1
            }
            if (!seen.has(neighbour)) {
                seen.add(neighbour)
                queue.push([neighbour, level + 1])
            }
        }
    }
}
return 0