0126. Word Ladder II.js

// Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

// Only one letter can be changed at a time
// Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
// Note:

// Return an empty list if there is no such transformation sequence.
// All words have the same length.
// All words contain only lowercase alphabetic characters.
// You may assume no duplicates in the word list.
// You may assume beginWord and endWord are non-empty and are not the same.

// Example 1:

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

// Output:
// [
//   ["hit","hot","dot","dog","cog"],
//   ["hit","hot","lot","log","cog"]
// ]

// Example 2:

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

// Output: []

// Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

// 1) BFS
/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {string[][]}
 */
const findLadders = (beginWord, endWord, wordList) => {
  const dict = new Set(wordList)
  const visited = new Set()
  const res = []
  const q = [[beginWord]]
  let step = Infinity
  while (q.length) {
    const path = q.shift()
    if (path.length === step) return res
    const w = path[path.length - 1]
    for (let i = 0; i < w.length; i++) {
      for (let j = 0; j < 26; j++) {
        const w2 = w.slice(0, i) + String.fromCharCode(97 + j) + w.slice(i + 1) // 97 -> 'a'
        if (dict.has(w2) && w2 !== w) {
          if (!visited.has(w2)) {
            q.push([...path, w2])
          }
          if (w2 === endWord) {
            if (path.length < step) {
              step = path.length + 1
            }
            res.push([...path, w2])
          }
        }
      }
    }
    visited.add(w)
  }
  return res
}
console.log(findLadders('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog']))