126. Word Ladder II

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.

Analyze

暂时跳过此题, 目前卡在 21/39 测试用例中, 超过时间限制;

/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {string[][]}
*/
var findLadders = function(beginWord, endWord, wordList) {
const result = []
if (wordList.indexOf(endWord) === -1) return result
const queue = []
const visitedObj = {
beginWord: {
visited: true,
visitedParent: null
}
}
queue.push({ word: createNode(beginWord), level: 1 })
let levelLimit = null
while (queue.length > 0) {
const { word, level } = queue.shift()
if (levelLimit && level >= levelLimit) return result
// if the value and it's parent value are visited, jump this loop;
if (visitedObj[word.val] && visitedObj[word.val].visited
&& word.parent === visitedObj[word.val].visitedParent) continue
for (let i = 0; i < wordList.length; i++) {
const isDiffOneWord = ifDiffOneWord(word.val, wordList[i])
if (isDiffOneWord) {
const newNode = createNode(wordList[i])
newNode.parent = word
if (wordList[i] === endWord) {
result.push(convertTreeToArr(newNode, beginWord))
levelLimit = level + 1
}
queue.push({ word: newNode, level: level + 1 })
visitedObj[word.val] = {
visited: true,
visitedParent: word
}
}
}
}
return result
}
// judge if the targetWord has one different word from the comparedWord;
function ifDiffOneWord(targetWord, comparedWord) {
let wordLength = targetWord.length
let diffNum = 0
for (let i = 0; i < wordLength; i++) {
if (targetWord[i] !== comparedWord[i]) {
diffNum++
}
if (diffNum > 1) return false
}
if (diffNum === 1) {
return true
} else {
return false
}
}
/**
* create new Node
*/
function createNode(val) {
return {
val,
parent: null
}
}
/**
* convert tree to arr
*/
function convertTreeToArr(tree, beginWord) {
const result = []
while (tree.parent) {
result.unshift(tree.val)
tree = tree.parent
}
result.unshift(beginWord)
return result
}

Similar Title

279、127、126