class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
}
};
127. 单词接龙
字典 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 中的所有字符串 互不相同原站题解
python3 解法, 执行用时: 144 ms, 内存消耗: 20.3 MB, 提交时间: 2022-08-01 11:11:03
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
def addWord(word: str):
if word not in wordId:
nonlocal nodeNum
wordId[word] = nodeNum
nodeNum += 1
def addEdge(word: str):
addWord(word)
id1 = wordId[word]
chars = list(word)
for i in range(len(chars)):
tmp = chars[i]
chars[i] = "*"
newWord = "".join(chars)
addWord(newWord)
id2 = wordId[newWord]
edge[id1].append(id2)
edge[id2].append(id1)
chars[i] = tmp
wordId = dict()
edge = collections.defaultdict(list)
nodeNum = 0
for word in wordList:
addEdge(word)
addEdge(beginWord)
if endWord not in wordId:
return 0
dis = [float("inf")] * nodeNum
beginId, endId = wordId[beginWord], wordId[endWord]
dis[beginId] = 0
que = collections.deque([beginId])
while que:
x = que.popleft()
if x == endId:
return dis[endId] // 2 + 1
for it in edge[x]:
if dis[it] == float("inf"):
dis[it] = dis[x] + 1
que.append(it)
return 0
python3 解法, 执行用时: 124 ms, 内存消耗: 20.6 MB, 提交时间: 2022-08-01 11:10:44
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
def addWord(word: str):
if word not in wordId:
nonlocal nodeNum
wordId[word] = nodeNum
nodeNum += 1
def addEdge(word: str):
addWord(word)
id1 = wordId[word]
chars = list(word)
for i in range(len(chars)):
tmp = chars[i]
chars[i] = "*"
newWord = "".join(chars)
addWord(newWord)
id2 = wordId[newWord]
edge[id1].append(id2)
edge[id2].append(id1)
chars[i] = tmp
wordId = dict()
edge = collections.defaultdict(list)
nodeNum = 0
for word in wordList:
addEdge(word)
addEdge(beginWord)
if endWord not in wordId:
return 0
disBegin = [float("inf")] * nodeNum
beginId = wordId[beginWord]
disBegin[beginId] = 0
queBegin = collections.deque([beginId])
disEnd = [float("inf")] * nodeNum
endId = wordId[endWord]
disEnd[endId] = 0
queEnd = collections.deque([endId])
while queBegin or queEnd:
queBeginSize = len(queBegin)
for _ in range(queBeginSize):
nodeBegin = queBegin.popleft()
if disEnd[nodeBegin] != float("inf"):
return (disBegin[nodeBegin] + disEnd[nodeBegin]) // 2 + 1
for it in edge[nodeBegin]:
if disBegin[it] == float("inf"):
disBegin[it] = disBegin[nodeBegin] + 1
queBegin.append(it)
queEndSize = len(queEnd)
for _ in range(queEndSize):
nodeEnd = queEnd.popleft()
if disBegin[nodeEnd] != float("inf"):
return (disBegin[nodeEnd] + disEnd[nodeEnd]) // 2 + 1
for it in edge[nodeEnd]:
if disEnd[it] == float("inf"):
disEnd[it] = disEnd[nodeEnd] + 1
queEnd.append(it)
return 0