Leetcode•Oct 08, 2025

Word Ladder

Hazrat Ali

Leetcode

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.


Solution
/**
 * Bidirectional BFS
 *
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
const ladderLength = (beginWord, endWord, wordList) => {
 
  const dict = new Set(wordList);

  if (!dict.has(endWord)) {
    return 0;
  }

  let head = new Set([beginWord]);
  let tail = new Set([endWord]);
  let distance = 2;

  dict.delete(beginWord);
  dict.delete(endWord);

  while (head.size > 0 && tail.size > 0) {
    if (head.size > tail.size) {
      [head, tail] = [tail, head];
    }

    const temp = new Set();

    for (let [word] of head.entries()) {
      const characters = word.split('');

      for (let i = 0; i < characters.length; i++) {
        const char = characters[i];

        for (let j = 0; j < 26; j++) {
          characters[i] = String.fromCharCode(97 + j);
          const newWord = characters.join('');

          if (newWord === word) {
            continue;
          }

          if (tail.has(newWord)) {
            return distance;
          }

          if (dict.has(newWord)) {
            dict.delete(newWord);
            temp.add(newWord);
          }
        }

        characters[i] = char;
      }
    }

    distance++;

    head = temp;
  }

  return 0;
};





Comments