1 题目描述
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的长度 5。
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: 0
解释: endWord "cog" 不在字典中，所以无法进行转换。
2 题解
简单来说就是求图的两点最短路径，每个单词看成一个点，只有相差一个字符的点之间才有路径，路径权值全部为1.
2.1 BFS
广度优先搜素是最直观的，但是这个超时了。。。
class Solution:
def ladder_length(self, beginWord: str, endWord: str, wordList: [str]) -> int:
from queue import Queue
queue = Queue()
wordList_len = len(wordList)
word_len = len(beginWord)
""" 用来标记wordList中的元素是否遍历过 """
flag = [1 for i in range(wordList_len)]
res = 1
queue.put(beginWord)
def can_change(str1, str2):
"""
判断 str1 和 str2 是否 对应位置只有一位不相等
:param str1:
:param str2:
:return:
"""
return sum(1 if str1[i] != str2[i] else 0 for i in range(word_len)) == 1
while queue.not_empty:
res += 1
size = queue.qsize()
while size > 0:
head_str = queue.get()
for i in range(wordList_len):
""" 该元素已经遍历过, 跳过 """
if flag[i] == 0:
continue
val = wordList[i]
""" 是联通的 """
if can_change(head_str, val):
if val == endWord:
return res
queue.put(val)
flag[i] = 0
size -= 1
return 0
def main(self):
# beginWord = "b"
# endWord = "e"
# wordList = ["a","e"]
beginWord = "teach"
endWord = "place"
wordList = ["peale", "wilts", "place", "fetch", "purer", "pooch", "peace", "poach", "berra", "teach", "rheum",
"peach"]
print(self.ladder_length(beginWord, endWord, wordList))
if __name__ == '__main__':
solution = Solution()
solution.main()2.2 暴力
别人的一种解法 作者此题评论区 habbi
思路：每次拿到一个节点时生成所有可能的下一个节点(可联通的)，新生成的节点只要再列表中就参与计算
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
l = len(endWord)
ws = set(wordList)
head = {beginWord}
tail = {endWord}
tmp = list('abcdefghijklmnopqrstuvwxyz')
res = 1
while head:
if len(head) > len(tail):
head, tail = tail, head
q = set()
for cur in head:
for i in range(l):
for j in tmp:
word = cur[:i] + j + cur[i+1:]
if word in tail:
return res + 1
if word in ws:
q.add(word)
ws.remove(word)
head = q
res += 1
return 0
