Leetcode 127, "Word Ladder" with Promises as a queue

127-word-ladder.js

/* https://leetcode.com/problems/word-ladder/ */

const checkAdjacency = (a, b) => {
  if (a.length !== b.length) {
    return false;
  }

  let first = true;
  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) {
      if (first) first = false;
      else return false;
    }
  }
  return true;
};

function ladderLength(beginWord, endWord, wordList) {
  wordList.push(beginWord);
  const adjacency = [];

  for (let i = 0; i < wordList.length; i++) {
    adjacency[i] ||= Array(i).fill(0);
    for (let j = 0; j < i; j++) {
      adjacency[i][j] = checkAdjacency(wordList[i], wordList[j]);
    }
  }

  let min = Infinity;
  const visited = Array(wordList.length).fill(false);
  const findAdjacent = (i, s) => {
    if (wordList[i] === endWord) min = Math.min(min, s);

    for (let j = 0; j < wordList.length; j++) {
      const isAdj = j < i ? adjacency[i][j] : adjacency[j][i];
      if (isAdj && !visited[j]) {
        visited[j] = true;
        // Sync promise execution is just a queue
        new Promise((res) => res(findAdjacent(j, s + 1)));
      }
    }
  };

  findAdjacent(wordList.length - 1, 0);

  return new Promise((res) => res(min === Infinity ? 0 : min));
}

console.log(
  await ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"])
);
// 5