127. Word Ladder
從單詞 beginWord 到單詞 endWord 的轉換序列使用字典 wordList 是一個單詞序列 beginWord -> s1 -> s2 -> ... -> sk，滿足以下條件：
每一對相鄰的單詞僅差一個字母。 每個 si（1 <= i <= k）都在 wordList 中。注意，beginWord 不需要在 wordList 中。 sk 等於 endWord。 給定兩個單詞 beginWord 和 endWord，以及一個字典 wordList，返回從 beginWord 到 endWord 的最短轉換序列中的單詞數，若不存在這樣的序列則返回 0。
範例：
輸入：beginWord = "hit"，endWord = "cog"，wordList = ["hot","dot","dog","lot","log","cog"] 輸出：5 解釋：一個最短的轉換序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，這個序列包含 5 個單詞。
Python
from collections import deque
from typing import List
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
wordSet = set(wordList)
if endWord not in wordSet:
return 0
queue = deque([(beginWord, 1)])
if beginWord in wordSet:
wordSet.remove(beginWord)
while queue:
current_word, length = queue.popleft()
for i in range(len(current_word)):
for char in 'abcdefghijklmnopqrstuvwxyz':
next_word = current_word[:i] + char + current_word[i + 1:]
if next_word == endWord:
return length + 1
if next_word in wordSet:
queue.append((next_word, length + 1))
wordSet.remove(next_word)
return 0
18.10MB, 342ms
C++
#include <vector>
#include <string>
#include <unordered_set>
#include <queue>
using namespace std;
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if (wordSet.find(endWord) == wordSet.end()) {
return 0;
}
queue<pair<string, int>> q;
q.push({beginWord, 1});
if (wordSet.find(beginWord) != wordSet.end()) {
wordSet.erase(beginWord);
}
while (!q.empty()) {
auto [currentWord, length] = q.front();
q.pop();
for (int i = 0; i < currentWord.size(); ++i) {
string original = currentWord;
for (char c = 'a'; c <= 'z'; ++c) {
if (currentWord[i] == c) continue;
currentWord[i] = c;
if (currentWord == endWord) {
return length + 1;
}
if (wordSet.find(currentWord) != wordSet.end()) {
q.push({currentWord, length + 1});
wordSet.erase(currentWord);
}
}
currentWord[i] = original[i];
}
}
return 0;
}
};
19.41MB, 68ms
Javascript
/**
* @param {string} beginWord
* @param {string} endWord
* @param {string[]} wordList
* @return {number}
*/
var ladderLength = function(beginWord, endWord, wordList) {
const wordSet = new Set(wordList);
if (!wordSet.has(endWord)) return 0;
const queue = [[beginWord, 1]];
if (wordSet.has(beginWord)) wordSet.delete(beginWord);
while (queue.length > 0) {
const [currentWord, length] = queue.shift();
for (let i = 0; i < currentWord.length; i++) {
const originalChar = currentWord[i];
for (let charCode = 97; charCode <= 122; charCode++) {
const char = String.fromCharCode(charCode);
if (char === originalChar) continue;
const nextWord = currentWord.slice(0, i) + char + currentWord.slice(i + 1);
if (nextWord === endWord) return length + 1;
if (wordSet.has(nextWord)) {
queue.push([nextWord, length + 1]);
wordSet.delete(nextWord);
}
}
}
}
return 0;
};
58.58MB, 192ms
