题目描述
在字典（单词列表） wordList 中，从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
- 序列中第一个单词是
beginWord 。
- 序列中最后一个单词是
endWord 。
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典
wordList 中的单词。
给定两个长度相同但内容不同的单词 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 中的所有字符串 互不相同
注意：本题与主站 127 题相同： https://leetcode.cn/problems/word-ladder/
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
words = set(wordList)
q = deque([beginWord])
ans = 1
while q:
n = len(q)
for _ in range(n):
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 + 1
q.append(t)
words.remove(t)
s[i] = ch
ans += 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 | class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
Queue<String> q = new LinkedList<>();
q.offer(beginWord);
int ans = 1;
while (!q.isEmpty()) {
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 + 1;
}
q.offer(t);
words.remove(t);
}
chars[j] = ch;
}
}
++ans;
}
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()) {
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 + 1;
q.push(s);
words.erase(s);
}
s[j] = ch;
}
}
++ans;
}
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 {
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 + 1
}
q = append(q, t)
words[t] = false
}
chars[j] = ch
}
}
ans++
}
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 {
func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
var words = Set(wordList)
var queue = [beginWord]
var ans = 1
while !queue.isEmpty {
for _ in 0..<queue.count {
let s = queue.removeFirst()
var chars = Array(s)
for j in 0..<chars.count {
let ch = chars[j]
for k in 0..<26 {
chars[j] = Character(UnicodeScalar(k + 97)!)
let t = String(chars)
if !words.contains(t) {
continue
}
if t == endWord {
return ans + 1
}
queue.append(t)
words.remove(t)
}
chars[j] = ch
}
}
ans += 1
}
return 0
}
}
|