1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
function dfs(    current: string,    res: string[][],    edge: Map<string, Set<string>>,    length: number,    path: string[],    endWord: string,    wordlevel: Map<string, number>,) {    if (path.length > length) return;    if (current === endWord && path.length === length) {        res.push([...path].reverse());        return;    }
    for (const next of edge.get(current) ?? []) {        if ((wordlevel.get(next) ?? 0) + 1 === wordlevel.get(current)) {            path.push(next);            dfs(next, res, edge, length, path, endWord, wordlevel);            path.pop();        }    }}function findLadders(    beginWord: string,    endWord: string,    wordList: string[],): string[][] {    const res: string[][] = [];
    const dict = new Set(wordList);    if (!dict.has(endWord)) {        return res;    }
    const edge = buildEdge([...wordList, beginWord]);
    const wordlevel = new Map<string, number>([]);
    const length = ladderLength(beginWord, endWord, wordList, edge, wordlevel);    if (!length) return [];    wordlevel.set(endWord, length - 1);    wordlevel.set(beginWord, 0);
    const current = endWord;    const path: string[] = [current];
    dfs(current, res, edge, length, path, beginWord, wordlevel);    return res;}function ladderLength(    beginWord: string,    endWord: string,    wordList: string[],    edge: Map<string, Set<string>>,    wordlevel: Map<string, number>,): number {    const words = new Set(wordList);    if (!words.has(endWord)) return 0;
    if (beginWord.length === 1) return 2;
    let current = [beginWord];    let step = 1;    let level = 0;    wordlevel.set(beginWord, 0);    while (current.length) {        level++;        const temp: string[] = [];
        for (const word of current) {            for (const other of words) {                if (edge.get(other)?.has(word)) {                    if (other === endWord) return step + 1;                    temp.push(other);                    wordlevel.set(other, level);                    words.delete(other);                }            }        }
        current = temp;        step = step + 1;    }
    return 0;}function diffOneChar(word1: string, word2: string): boolean {    let changes = 0;    for (let i = 0; i < word1.length; i++) {        if (word1[i] != word2[i]) changes += 1;    }    return changes === 1;}function buildEdge(wordList: string[]): Map<string, Set<string>> {    const edge = new Map<string, Set<string>>();    for (let i = 0; i < wordList.length; i++) {        for (let j = i + 1; j < wordList.length; j++) {            if (diffOneChar(wordList[i], wordList[j])) {                addEdge(edge, wordList[i], wordList[j]);                addEdge(edge, wordList[j], wordList[i]);            }        }    }    return edge;}
function addEdge(edge: Map<string, Set<string>>, word1: string, word2: string) {    const set = edge.get(word1) ?? new Set();    set.add(word2);    edge.set(word1, set);}export default findLadders;