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


	Every adjacent pair of words differs by a single letter.
	Every si for 1 &lt;= i &lt;= 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.

&nbsp;
Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -&gt; "hot" -&gt; "dot" -&gt; "dog" -&gt; 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.


&nbsp;
Constraints:


	1 &lt;= beginWord.length &lt;= 10
	endWord.length == beginWord.length
	1 &lt;= wordList.length &lt;= 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.


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        e = defaultdict(list)
        m = len(beginWord)
        for word in wordList + [beginWord]:
            for i in range(m):
                w = word[:i] + "*" + word[i + 1:]
                e[w].append(word)
        q = deque([beginWord])
        used = set([beginWord])
        d = 0
        while q:
            d += 1
            for _ in range(len(q)):
                word = q.popleft()
                for i in range(m):
                    w = word[:i] + "*" + word[i + 1:]
                    if w in e:
                        for v in e[w]:
                            if v == endWord:
                                return d + 1
                            if v not in used:
                                q.append(v)
                                used.add(v)
                        e.pop(w)
        return 0
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int count = 1;
        Set<String> words = new HashSet<>(wordList);
        Queue<String> q = new LinkedList<String>();
        q.add(beginWord);
        
        while(!q.isEmpty()) {
            int size = q.size();
            
            while(size-- > 0) {
                String word = q.poll();
                char[] chList = word.toCharArray();
                
                for(int i=0; i<word.length(); i++) {
                    char tmp = chList[i];
                    
                    for(char c='a'; c<='z'; c++) {
                        chList[i] = c;
                        String newWord = new String(chList);
                        
                        if(words.contains(newWord)) {
                            if(newWord.equals(endWord)) {
                                return count + 1;
                            }
                            q.add(newWord);
                            words.remove(newWord);
                        }
                    }
                    
                    chList[i] = tmp;
                }
            }
            
            count++;
        }
        
        return 0;
    }
}
// For approach: ref: https://www.youtube.com/watch?v=ZVJ3asMoZ18&t=0s

class Solution
{
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList)
    {
        // 1. Create a set and insert all wordList to the set to have
        // easy search of O(1)
        unordered_set<string> wordSet;
        bool isEndWordPresent = false;
        for (string s:wordList)
        {
            // Check if the destination string even present in the wordList
            // If not then there is no point in even trying to find the
            // route from source string to destination string
            if (!isEndWordPresent && s.compare(endWord) == 0)
            {
                isEndWordPresent = true;
            }
            wordSet.insert(s);
        }

        // 2. If endWord is not present in the wordList return
        if (!isEndWordPresent)
        {
            return 0;
        }

        // 3. Create a queue for BST insert the elements of currentlevel to the queue
        // currentLevel is defined as all the strings that can be reached from
        // all the strings of the previous string by just replacing one character
        // and the one-char-replaced-string is present in the wordSet / wordList
        queue<string> q;
        q.push(beginWord);
        int level = 0; // every time all the strings at this level are processed increment it

        // 4. Loop through all the elements in the queue
        while (!q.empty())
        {
            level++;
            int numStringsInCurLevel = q.size();
            // loop through all the strings in this current level
            // and find out if destination can be reached before
            // jumping to the next level of strings added to the queue
            while (numStringsInCurLevel--)
            {
                string curStr = q.front();
                q.pop();

                for (int i=0; i<curStr.length(); i++)
                {
                    string tempStr = curStr;
                    // Now check if swappin one char in the curStr will
                    // lead to any string in the wordSet
                    for (char c='a'; c<='z'; c++)
                    {
                        tempStr[i] = c;
                        if (tempStr.compare(curStr) == 0)
                        {
                            // Ignore the same string
                            continue;
                        }
                        // Check if we reached the destination
                        if (tempStr.compare(endWord) == 0)
                        {
                            return level+1;
                        }
                        if (wordSet.find(tempStr) != wordSet.end())
                        {
                            // this string is in the set so add it to the queue
                            // and remove it from the set
                            q.push(tempStr);
                            wordSet.erase(tempStr);
                        }
                    }
                }
            }
        }

        // If we are here then we couldn't reach destination
        // even though the destination string is present in the wordList
        // there is no path from source to destination for the given rules
        return 0;
    }
};
/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */

// Logic is same as One direction, just from both side tword mid, much faster.
// One Direction solution is here ->
// https://leetcode.com/problems/word-ladder/discuss/2372376/Easy-Fast-Simple-83.95-235-ms-50.4-MB-One-Direction

var ladderLength = function(beginWord, endWord, wordList) {
    const charMap = buildCharMap()
    const wordSet = new Set(wordList)
    if (!wordSet.has(endWord)) return 0

    let leftSet = new Set([beginWord]), rightSet = new Set([endWord]), level = 1
    
    const helper = (set1, set2) => {
        const setArr = Array.from(set1)
        for (let i = 0;  i < setArr.length; i++) {
            const word = setArr[i]
            for (let i = 0; i < word.length; i++) {
                for (const c of charMap) {
                    const newWord = word.slice(0, i) + c + word.slice(i + 1)

                    if (set2.has(newWord)) return true
                    if (wordSet.has(newWord)) { 
                        set1.add(newWord)
                        wordSet.delete(newWord)
                    }
                }
            }
            set1.delete(word)
        }
    }
    
    while (leftSet.size && rightSet.size) {
        level++
        if (helper(leftSet, rightSet)) return level
        
        level++
        if (helper(rightSet, leftSet)) return level
    }
        
    return 0
};

const buildCharMap = () => {
    const map = []
    
    for (let i = 0; i < 26; i++) {
        map.push(String.fromCharCode(i + 97))
    }
    
    return map
}
Word Ladder