1
const isMatch = (currWord, nextWord) => {
2
  let mismatch = 0;
3
  for (let i = 0; i < nextWord.length; i += 1) {
4
    if (nextWord[i] !== currWord[i]) {
5
      mismatch += 1;
6
    }
7
  }
8

9
  return mismatch === 1;
10
};
11

12
const getNextWords = (lastRung, dictionary) => {
13
  const nextWords = [];
14
  for (const word of dictionary) {
15
    if (isMatch(word, lastRung)) {
16
      nextWords.push(word);
17
    }
18
  }
19

20
  return nextWords;
21
};
22

23
const updateLadders = (ladders, dictionary) => {
24
  const updatedLadders = [];
25
  const nextRung = new Set();
26

27
  for (const ladder of ladders) {
28
    const nextWords = getNextWords(ladder[ladder.length - 1], dictionary);
29
    for (const nextWord of nextWords) {
30
      updatedLadders.push([...ladder, nextWord]);
31
      nextRung.add(nextWord);
32
    }
33
  }
34

35
  return [updatedLadders, nextRung];
36
};
37

38
const updateDictionary = (dictionary, nextRung) => {
39
  return dictionary.filter((word) => !nextRung.has(word));
40
};
41

42
// BFS traversal from endWord to beginWord
43
// This limits the paths that we'll need to consider during our traversal from beingWord to endWord
44
const getDictionary = (wordList, endWord, beginWord) => {
45
  const dictionary = new Set();
46

47
  let currRung = [endWord];
48
  while (currRung.length > 0) {
49
    const nextRung = new Set();
50
    if (!wordList.includes(beginWord)) break;
51

52
    while (currRung.length > 0) {
53
      const currWord = currRung.pop();
54
      dictionary.add(currWord);
55

56
      for (const nextWord of wordList) {
57
        if (isMatch(currWord, nextWord)) {
58
          nextRung.add(nextWord);
59
        }
60
      }
61
    }
62

63
    currRung = [...nextRung];
64
    wordList = wordList.filter((word) => !nextRung.has(word));
65
  }
66

67
  return [...dictionary];
68
};
69

70
var findLadders = function (beginWord, endWord, wordList) {
71
  if (!wordList.includes(endWord)) return [];
72
  if (!wordList.includes(beginWord)) wordList.push(beginWord);
73

74
  const result = [];
75
  const saveResult = (ladders) => {
76
    for (const ladder of ladders) {
77
      if (ladder[ladder.length - 1] === endWord) {
78
        result.push(ladder);
79
      }
80
    }
81
  };
82

83
  let ladders = [[beginWord]];
84
  let dictionary = getDictionary(wordList, endWord, beginWord);
85
  while (ladders.length > 0) {
86
    if (!dictionary.includes(endWord)) {
87
      saveResult(ladders);
88
      break;
89
    }
90

91
    const [updatedLadders, nextRung] = updateLadders(ladders, dictionary);
92
    ladders = updatedLadders;
93
    dictionary = updateDictionary(dictionary, nextRung);
94
  }
95

96
  return result;
97
};