题目描述
字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：
- 每一对相邻的单词只差一个字母。
- 对于
1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
示例 1：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
示例 2：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。
提示：
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord、endWord 和 wordList[i] 由小写英文字母组成beginWord != endWordwordList 中的所有字符串 互不相同
解法
方法一：BFS
BFS 最小步数模型。本题可以用朴素 BFS，也可以用双向 BFS 优化搜索空间，从而提升效率。
双向 BFS 是 BFS 常见的一个优化方法，主要实现思路如下：
- 创建两个队列 q1, q2 分别用于“起点 -> 终点”、“终点 -> 起点”两个方向的搜索；
- 创建两个哈希表 m1, m2 分别记录访问过的节点以及对应的扩展次数（步数）；
- 每次搜索时，优先选择元素数量较少的队列进行搜索扩展，如果在扩展过程中，搜索到另一个方向已经访问过的节点，说明找到了最短路径；
- 只要其中一个队列为空，说明当前方向的搜索已经进行不下去了，说明起点到终点不连通，无需继续搜索。
while q1 and q2:
if len(q1) <= len(q2):
# 优先选择较少元素的队列进行扩展
extend(m1, m2, q1)
else:
extend(m2, m1, q2)
def extend(m1, m2, q):
# 新一轮扩展
for _ in range(len(q)):
p = q.popleft()
step = m1[p]
for t in next(p):
if t in m1:
# 此前已经访问过
continue
if t in m2:
# 另一个方向已经搜索过，说明找到了一条最短的连通路径
return step + 1 + m2[t]
q.append(t)
m1[t] = step + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words = set(wordList)
q = deque([beginWord])
ans = 1
while q:
ans += 1
for _ in range(len(q)):
s = q.popleft()
s = list(s)
for i in range(len(s)):
ch = s[i]
for j in range(26):
s[i] = chr(ord('a') + j)
t = ''.join(s)
if t not in words:
continue
if t == endWord:
return ans
q.append(t)
words.remove(t)
s[i] = ch
return 0
|
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 | class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
Queue<String> q = new ArrayDeque<>();
q.offer(beginWord);
int ans = 1;
while (!q.isEmpty()) {
++ans;
for (int i = q.size(); i > 0; --i) {
String s = q.poll();
char[] chars = s.toCharArray();
for (int j = 0; j < chars.length; ++j) {
char ch = chars[j];
for (char k = 'a'; k <= 'z'; ++k) {
chars[j] = k;
String t = new String(chars);
if (!words.contains(t)) {
continue;
}
if (endWord.equals(t)) {
return ans;
}
q.offer(t);
words.remove(t);
}
chars[j] = ch;
}
}
}
return 0;
}
}
|
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 | class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
queue<string> q{{beginWord}};
int ans = 1;
while (!q.empty()) {
++ans;
for (int i = q.size(); i > 0; --i) {
string s = q.front();
q.pop();
for (int j = 0; j < s.size(); ++j) {
char ch = s[j];
for (char k = 'a'; k <= 'z'; ++k) {
s[j] = k;
if (!words.count(s)) continue;
if (s == endWord) return ans;
q.push(s);
words.erase(s);
}
s[j] = ch;
}
}
}
return 0;
}
};
|
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 | func ladderLength(beginWord string, endWord string, wordList []string) int {
words := make(map[string]bool)
for _, word := range wordList {
words[word] = true
}
q := []string{beginWord}
ans := 1
for len(q) > 0 {
ans++
for i := len(q); i > 0; i-- {
s := q[0]
q = q[1:]
chars := []byte(s)
for j := 0; j < len(chars); j++ {
ch := chars[j]
for k := 'a'; k <= 'z'; k++ {
chars[j] = byte(k)
t := string(chars)
if !words[t] {
continue
}
if t == endWord {
return ans
}
q = append(q, t)
words[t] = false
}
chars[j] = ch
}
}
}
return 0
}
|
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 | using System.Collections;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
var words = Enumerable.Repeat(beginWord, 1).Concat(wordList).Select((word, i) => new { Word = word, Index = i }).ToList();
var endWordIndex = words.Find(w => w.Word == endWord)?.Index;
if (endWordIndex == null) {
return 0;
}
var paths = new List<int>[words.Count];
for (var i = 0; i < paths.Length; ++i)
{
paths[i] = new List<int>();
}
for (var i = 0; i < beginWord.Length; ++i)
{
var hashMap = new Hashtable();
foreach (var item in words)
{
var newWord = string.Format("{0}_{1}", item.Word.Substring(0, i), item.Word.Substring(i + 1));
List<int> similars;
if (!hashMap.ContainsKey(newWord))
{
similars = new List<int>();
hashMap.Add(newWord, similars);
}
else
{
similars = (List<int>)hashMap[newWord];
}
foreach (var similar in similars)
{
paths[similar].Add(item.Index);
paths[item.Index].Add(similar);
}
similars.Add(item.Index);
}
}
var left = words.Count - 1;
var lastRound = new List<int> { 0 };
var visited = new bool[words.Count];
visited[0] = true;
for (var result = 2; left > 0; ++result)
{
var thisRound = new List<int>();
foreach (var index in lastRound)
{
foreach (var next in paths[index])
{
if (!visited[next])
{
visited[next] = true;
if (next == endWordIndex) return result;
thisRound.Add(next);
}
}
}
if (thisRound.Count == 0) break;
lastRound = thisRound;
}
return 0;
}
}
|
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 | function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
if (!wordList.includes(endWord)) return 0;
const replace = (s: string, i: number, ch: string) => s.slice(0, i) + ch + s.slice(i + 1);
const { length } = beginWord;
const words: Record<string, string[]> = {};
const g: Record<string, string[]> = {};
for (const w of [beginWord, ...wordList]) {
const derivatives: string[] = [];
for (let i = 0; i < length; i++) {
const nextW = replace(w, i, '*');
derivatives.push(nextW);
g[nextW] ??= [];
g[nextW].push(w);
}
words[w] = derivatives;
}
let ans = 0;
let q = words[beginWord];
const vis = new Set<string>([beginWord]);
while (q.length) {
const nextQ: string[] = [];
ans++;
for (const variant of q) {
for (const w of g[variant]) {
if (w === endWord) return ans + 1;
if (vis.has(w)) continue;
vis.add(w);
nextQ.push(...words[w]);
}
}
q = nextQ;
}
return 0;
}
|
方法二
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 | class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
def extend(m1, m2, q):
for _ in range(len(q)):
s = q.popleft()
step = m1[s]
s = list(s)
for i in range(len(s)):
ch = s[i]
for j in range(26):
s[i] = chr(ord('a') + j)
t = ''.join(s)
if t in m1 or t not in words:
continue
if t in m2:
return step + 1 + m2[t]
m1[t] = step + 1
q.append(t)
s[i] = ch
return -1
words = set(wordList)
if endWord not in words:
return 0
q1, q2 = deque([beginWord]), deque([endWord])
m1, m2 = {beginWord: 0}, {endWord: 0}
while q1 and q2:
t = extend(m1, m2, q1) if len(q1) <= len(q2) else extend(m2, m1, q2)
if t != -1:
return t + 1
return 0
|
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 | class Solution {
private Set<String> words;
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
words = new HashSet<>(wordList);
if (!words.contains(endWord)) {
return 0;
}
Queue<String> q1 = new ArrayDeque<>();
Queue<String> q2 = new ArrayDeque<>();
Map<String, Integer> m1 = new HashMap<>();
Map<String, Integer> m2 = new HashMap<>();
q1.offer(beginWord);
q2.offer(endWord);
m1.put(beginWord, 0);
m2.put(endWord, 0);
while (!q1.isEmpty() && !q2.isEmpty()) {
int t = q1.size() <= q2.size() ? extend(m1, m2, q1) : extend(m2, m1, q2);
if (t != -1) {
return t + 1;
}
}
return 0;
}
private int extend(Map<String, Integer> m1, Map<String, Integer> m2, Queue<String> q) {
for (int i = q.size(); i > 0; --i) {
String s = q.poll();
int step = m1.get(s);
char[] chars = s.toCharArray();
for (int j = 0; j < chars.length; ++j) {
char ch = chars[j];
for (char k = 'a'; k <= 'z'; ++k) {
chars[j] = k;
String t = new String(chars);
if (!words.contains(t) || m1.containsKey(t)) {
continue;
}
if (m2.containsKey(t)) {
return step + 1 + m2.get(t);
}
q.offer(t);
m1.put(t, step + 1);
}
chars[j] = ch;
}
}
return -1;
}
}
|
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 | class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> words(wordList.begin(), wordList.end());
if (!words.count(endWord)) return 0;
queue<string> q1{{beginWord}};
queue<string> q2{{endWord}};
unordered_map<string, int> m1;
unordered_map<string, int> m2;
m1[beginWord] = 0;
m2[endWord] = 0;
while (!q1.empty() && !q2.empty()) {
int t = q1.size() <= q2.size() ? extend(m1, m2, q1, words) : extend(m2, m1, q2, words);
if (t != -1) return t + 1;
}
return 0;
}
int extend(unordered_map<string, int>& m1, unordered_map<string, int>& m2, queue<string>& q, unordered_set<string>& words) {
for (int i = q.size(); i > 0; --i) {
string s = q.front();
int step = m1[s];
q.pop();
for (int j = 0; j < s.size(); ++j) {
char ch = s[j];
for (char k = 'a'; k <= 'z'; ++k) {
s[j] = k;
if (!words.count(s) || m1.count(s)) continue;
if (m2.count(s)) return step + 1 + m2[s];
m1[s] = step + 1;
q.push(s);
}
s[j] = ch;
}
}
return -1;
}
};
|
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 | func ladderLength(beginWord string, endWord string, wordList []string) int {
words := make(map[string]bool)
for _, word := range wordList {
words[word] = true
}
if !words[endWord] {
return 0
}
q1, q2 := []string{beginWord}, []string{endWord}
m1, m2 := map[string]int{beginWord: 0}, map[string]int{endWord: 0}
extend := func() int {
for i := len(q1); i > 0; i-- {
s := q1[0]
step, _ := m1[s]
q1 = q1[1:]
chars := []byte(s)
for j := 0; j < len(chars); j++ {
ch := chars[j]
for k := 'a'; k <= 'z'; k++ {
chars[j] = byte(k)
t := string(chars)
if !words[t] {
continue
}
if _, ok := m1[t]; ok {
continue
}
if v, ok := m2[t]; ok {
return step + 1 + v
}
q1 = append(q1, t)
m1[t] = step + 1
}
chars[j] = ch
}
}
return -1
}
for len(q1) > 0 && len(q2) > 0 {
if len(q1) > len(q2) {
m1, m2 = m2, m1
q1, q2 = q2, q1
}
t := extend()
if t != -1 {
return t + 1
}
}
return 0
}
|