126. Word Ladder II

[Tcdian]

126. Word Ladder II

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

1. 每次转换只能改变一个字母。
2. 转换过程中的中间单词必须是字典中的单词

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.

Note

• 如果不存在这样的转换序列，返回一个空列表。
• 所有单词具有相同的长度。
• 所有单词只由小写字母组成。
• 字典中不存在重复的单词。
• 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {string[][]}
 */
var findLadders = function(beginWord, endWord, wordList) {
    const result = [];
    const graph = createGraph([...new Set([beginWord, ...wordList])]);
    const queue = [[beginWord, 0, -1]];
    const visitedLevel = new Map();
    let queueIndex = 0;
    while (queueIndex !== queue.length) {
        const [word, level, prevIndex] = queue[queueIndex];
        if (word === endWord) {
            result.push(trackPath([word, level, prevIndex]));
        }
        const nextWords = graph.get(word);
        if (nextWords !== undefined) {
            for (let i = 0; i < nextWords.length; i++) {
                if (!visitedLevel.has(nextWords[i]) || visitedLevel.get(nextWords[i]) === level + 1) {
                    visitedLevel.set(nextWords[i], level + 1);
                    queue.push([nextWords[i], level + 1, queueIndex]);
                }
            }
        }
        queueIndex++;
    }
    return result;

    function canConnect(word1, word2) {
        let diffByteCount = 0;
        for (let i = 0; i < word1.length; i++) {
            if (word1[i] !== word2[i]) {
                diffByteCount++;
            }
            if (diffByteCount > 1) {
                return false;
            }
        }
        return diffByteCount === 1;
    }

    function createGraph(wordList) {
        const graph = new Map();
        for (let i = 0; i < wordList.length; i++) {
            for (let j = 0; j < wordList.length; j++) {
                if (canConnect(wordList[i], wordList[j])) {
                    graph.set(wordList[i], ([...graph.get(wordList[i]) || [], wordList[j]]));
                }
            }
        }
        return graph;
    }

    function trackPath(wordNode) {
        let path = [];
        while(wordNode[2] !== -1) {
            path.unshift(wordNode[0]);
            wordNode = queue[wordNode[2]];
        }
        path.unshift(wordNode[0]);
        return path;
    }
};

• TypeScript Solution

function findLadders(beginWord: string, endWord: string, wordList: string[]): string[][] {
    const result: string[][] = [];
    const graph = createGraph([...new Set([beginWord, ...wordList])]);
    const queue: [string, number, number][] = [[beginWord, 0, -1]];
    const visitedLevel: Map<string, number> = new Map();
    let queueIndex = 0;
    while (queueIndex !== queue.length) {
        const [word, level, prevIndex] = queue[queueIndex];
        if (word === endWord) {
            result.push(trackPath([word, level, prevIndex]));
        }
        const nextWords = graph.get(word);
        if (nextWords !== undefined) {
            for (let i = 0; i < nextWords.length; i++) {
                if (!visitedLevel.has(nextWords[i]) || visitedLevel.get(nextWords[i]) === level + 1) {
                    visitedLevel.set(nextWords[i], level + 1);
                    queue.push([nextWords[i], level + 1, queueIndex]);
                }
            }
        }
        queueIndex++;
    }
    return result;

    function canConnect(word1: string, word2: string): boolean {
        let diffByteCount = 0;
        for (let i = 0; i < word1.length; i++) {
            if (word1[i] !== word2[i]) {
                diffByteCount++;
            }
            if (diffByteCount > 1) {
                return false;
            }
        }
        return diffByteCount === 1;
    }

    function createGraph(wordList: string[]): Map<string, string[]> {
        const graph: Map<string, string[]> = new Map();
        for (let i = 0; i < wordList.length; i++) {
            for (let j = 0; j < wordList.length; j++) {
                if (canConnect(wordList[i], wordList[j])) {
                    graph.set(wordList[i], ([...graph.get(wordList[i]) || [], wordList[j]]));
                }
            }
        }
        return graph;
    }

    function trackPath(wordNode: [string, number, number]): string[] {
        let path: string[] = [];
        while(wordNode[2] !== -1) {
            path.unshift(wordNode[0]);
            wordNode = queue[wordNode[2]];
        }
        path.unshift(wordNode[0]);
        return path;
    }
}