Word Ladder Hard 0 attempts
LeetCode ↗

Word Ladder

Hard GraphBFSDFS LeetCode

Given beginWord, endWord, and a wordList, find the shortest transformation sequence length from beginWord to endWord, changing one letter at a time.

Example: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] → Output: 5

Sample Input
—
Sample Output
—
Constraints
  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
Test Cases
Case 1
Args: ["hit","cog",["hot","dot","dog","lot","log","cog"]] Expected: 5
Topics
GraphBFSDFS

BFS

function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  const q = [[beginWord, 1]];
  const visited = new Set([beginWord]);
  while (q.length) {
    const [word, len] = q.shift();
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {
        const next = word.slice(0,i) + String.fromCharCode(c) + word.slice(i+1);
        if (next === endWord) return len + 1;
        if (wordSet.has(next) && !visited.has(next)) {
          visited.add(next); q.push([next, len + 1]);
        }
      }
    }
  }
  return 0;
}

Time: O(M² × N) where M=word length, N=word list size | Space: O(M × N)

Saved in this browser only. Private to you.

JavaScript