leetcode单词接龙 127
给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则:
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列,返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的,且二者不相同。
示例 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" 不在字典中,所以无法进行转换。
第一种做法: 回溯法
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
if self.oneCh(beginWord, endWord):
return 2
#result[0]用来记录当前路径长度(或者深度)
#result[1]用来记录最小路径长度(或者深度)
result = [1, 100000000000]
self.f(beginWord, endWord, wordList,result)
return result[1] if result[1]!=100000000000 else 0
def f(self, beginWord, endWord, wordList, result):
l = len(wordList)
for i in range(l):
# self.oneCh(word1,word2)用来判断word1能否通过一个字母的改变变成word2
if self.oneCh(beginWord, wordList[i]):
#当前路径长度加1
result[0] = result[0] + 1
# 如果当前路径长度 >= 最小路径长度, 直接return
if result[0] >= result[1]:
result[0] = result[0] - 1
return
# 当前元素从列表中出去
cur = wordList.pop(i)
# 若当前单词==endWord,min(result[1],result[0], return
if cur == endWord:
result[1] = min(result[1], result[0])
print(result[1])
result[0] = result[0] - 1
wordList.insert(i,cur)
return
# 若cur!=endWord,且result[0] >= result[1]-1, 跳过递归self.f()函数
if result[0] < result[1] - 1:
self.f(cur,endWord,wordList, result)
# 重新把cur插入进来
wordList.insert(i, cur)
result[0] = result[0] - 1
def oneCh(self,cur, word):
i = 0
for j in range(len(cur)):
if cur[j] != word[j]:
i = i + 1
if i == 1:
return True
else:
return False
这种方法超时。
第二种: 不知道叫什么名字
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
if self.oneCh(beginWord, endWord):
return 2
word_Set = set()
result = 1
for i in wordList:
word_Set.add(i)
temp_set = set([endWord])
word_Set.remove(endWord)
while len(temp_set) != 0:
temp = set()
for i in temp_set:
for j in word_Set:
if self.oneCh(i, j):
if self.oneCh(j, beginWord):
return result + 2
temp.add(j)
for i in temp:
word_Set.remove(i)
temp_set = temp
result = result + 1
return 0
def oneCh(self,cur, word):
i = 0
for j in range(len(cur)):
if cur[j] != word[j]:
i = i + 1
if i == 1:
return True
else:
return False
直接配图:
也是超时了, 应该是
while len(temp_set) != 0:
temp = set()
for i in temp_set:
for j in word_Set:
if self.oneCh(i, j):
耗时较大
第三种: 和第二种的思想是一样的,不过是从前开始的,也对第二种的耗时较大的部分稍微修改了下:
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList:
return 0
word_Set = set()
result = 1
if self.oneCh(beginWord,endWord):
return result + 1
for i in wordList:
word_Set.add(i)
word_Set.add(beginWord)
n = len(beginWord)
temp_set = set([endWord])
word_Set.remove(endWord)
while len(temp_set) != 0:
temp = set()
for i in temp_set:
for t in range(n):
for e in 'abcdefghijklmnopqrstuvwxyz':
word = i[0:t] + e + i[t+1:n]
if word in word_Set:
temp.add(word)
for i in temp:
word_Set.remove(i)
temp_set = temp
if beginWord in temp_set:
return result + 1
result = result + 1
return 0