代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
字典 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 <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord
、endWord
和 wordList[i]
由小写英文字母组成beginWord != endWord
wordList
中的所有字符串 互不相同
BFS 最小步数模型。本题可以用朴素 BFS,也可以用双向 BFS 优化搜索空间,从而提升效率。
双向 BFS 是 BFS 常见的一个优化方法,主要实现思路如下:
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
朴素 BFS:
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
双向 BFS:
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
朴素 BFS:
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;
}
}
双向 BFS:
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;
}
}
朴素 BFS:
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;
}
};
双向 BFS:
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;
}
};
朴素 BFS:
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
}
双向 BFS:
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
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。