我正在尝试解决leetcode问题(https://leetcode.com/problems/word-ladder/description/):
给定两个单词(beginword和endword)和字典的单词列表,找出从beginword到endword的最短转换序列的长度,以便:
一次只能更改一个字母。
每个转换的单词必须存在于单词列表中。注意beginWord不是一个转换的单词。
注:
如果没有这样的转换序列,则返回0。
所有单词的长度都一样。
所有单词只包含小写字母字符。
您可以假定单词列表中没有重复的单词。
您可以假设beginword和endword是非空的,并且不相同。
输入:
beginword=“命中”,
endword=“COG”,
单词表=[“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出:
5个
说明:
因为最短的转换是“hit”->“hot”->“dot”->“dog”->
“cog”,返回其长度5。
import queue
class Solution:
def isadjacent(self,a, b):
count = 0
n = len(a)
for i in range(n):
if a[i] != b[i]:
count += 1
if count > 1:
return False
if count == 1:
return True
def ladderLength(self,beginWord, endWord, wordList):
word_queue = queue.Queue(maxsize=0)
word_queue.put((beginWord,1))
while word_queue.qsize() > 0:
queue_last = word_queue.get()
index = 0
while index != len(wordList):
if self.isadjacent(queue_last[0],wordList[index]):
new_len = queue_last[1]+1
if wordList[index] == endWord:
return new_len
word_queue.put((wordList[index],new_len))
wordList.pop(index)
index-=1
index+=1
return 0
有人能建议如何优化它和防止错误!
最佳答案
基本思想是更快地找到相邻的单词。不要考虑列表中的每个单词(即使是已经按单词长度筛选过的单词),而是构造每个可能的相邻字符串并检查它是否在字典中要快速查找,请确保单词列表存储在支持快速成员资格测试的set
中。
为了更快,您可以存储两个已排序的单词列表,其中一个按每个单词的相反顺序排序然后寻找可能涉及改变一个字母的前半部分在颠倒的名单和后半部分在正常的名单然后可以找到所有现有的邻居而不做任何非字符串。这甚至可以扩展到n个列表,每个列表通过从所有单词中省略一个字母进行排序。