127. Word Ladder

Problem

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

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

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

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

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

• Return 0 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.

Solution

BFS

Like building a tree, let beginWord be the root, then find all of its neighbors and let them be the children. Then do the same for the children, respectively.

We can delete every neighbor from the wordList as soon as we first meet it. Because if the word is in the final result, then the first time it appears is guaranteed to be the shortest.

To find neighbors, for wordList that has more than 26 words, list all the possible neighbors of the target word(word.length * 26 - 1), then check if they are in the wordList. Otherwise, just check every words in the wordList with isNeighbor() (compares (word.length * wordList.size) times).

/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function (beginWord, endWord, wordList) {
  wordList = new Set(wordList)

  var queue = [beginWord, null]
  var level = 1

  while (queue.length > 1) {
    // nodes of the old level
    let word = queue.shift()

    if (!word) {
      // new level
      level += 1
      queue.push(null)
      continue
    }

    if (isNeighbor(word, endWord)) {
      return level + 1
    }

    // find neighbors & push to queue
    findNeighbors(word)
  }

  function isNeighbor (w1, w2) {
    var isOneMisMatch = false
    for (let i = 0; i < w1.length; i += 1) {
      if (w1[i] !== w2[i]) {
        if (isOneMisMatch) { return false }
        isOneMisMatch = true
      }
    }
    return isOneMisMatch
  }

  function findNeighbors (word) {
    if (wordList.size <= 26) {
      wordList.forEach(w => {
        if (isNeighbor(word, w)) {
          queue.push(w)
          // we can safely delete it because
          // even if me meet it later
          // this is the shortest one
          wordList.delete(w)
        }
      })
    } else {
      // List all the possible neighbors
      // then check if they are in the wordList
      // compares (word.length * 26 - 1) times
      let wordCharCode = []
      for (let i = 0; i < word.length; i += 1) {
        wordCharCode.push(word.charCodeAt(i))
      }

      for (let i = 0; i < word.length; i += 1) {
        // store the current char code
        let curCode = wordCharCode[i]

        // repale the current char, from a to z
        for (let c = 97; c <= 122; c += 1) {
          if (c !== curCode) {
            wordCharCode[i] = c
            let genWord = String.fromCharCode(...wordCharCode)

            if (wordList.has(genWord)) {
              queue.push(genWord)
              wordList.delete(genWord)
            }
          }
        }

        // restore the current char code
        wordCharCode[i] = curCode
      }
    }
  }

  return 0
};