Word Ladder Hard 0 attempts
LeetCode ↗

Word Ladder

Hard GraphBFSDFS LeetCode

You're given beginWord, endWord, and a list wordList. Each step lets you change exactly one letter of the current word, and whatever word results must appear in wordList. Find how many words long the shortest such chain from beginWord to endWord is, counting both endpoints; if no such chain exists, the answer is 0.

Input Format
Implement ladderLength(beginWord, endWord, wordList). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

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

BFS

javascript
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]);
  let head = 0;
  while (head < q.length) {
    const [word, len] = q[head++];
    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