python - 超出时间限制错误。字梯 leetcode

Question

我正在尝试解决 leetcode 问题(https://leetcode.com/problems/word-ladder/description/):

给定两个单词(beginWord 和 endWord)和一个字典的单词列表，找到从 beginWord 到 endWord 的最短转换序列的长度，这样:

一次只能更改一个字母。 每个转换后的单词必须存在于单词列表中。请注意，beginWord 不是转换后的词。 注意:

如果不存在这样的转换序列则返回0。 所有单词的长度都相同。 所有单词仅包含小写字母字符。 您可以假设单词列表中没有重复项。 您可以假设 beginWord 和 endWord 非空且不相同。

输入:

beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

输出:

5

解释:

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 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

有人可以建议如何优化它并防止错误!

Answer 1

基本思想是更快地找到相邻的单词。不要考虑列表中的每个单词(即使是已经按单词长度过滤的单词)，而是构造每个可能的相邻字符串并检查它是否在字典中。要使这些 查找速度更快，请确保将单词列表存储在类似于支持快速成员资格测试的set 中。

为了更快，您可以存储两个排序的单词列表，一个按每个单词的反向排序。然后寻找涉及更改反转列表前半部分和正常列表后半部分字母的可能性。然后可以在不创建任何非单词字符串的情况下找到所有现有的邻居。这甚至可以扩展到 n 个列表，每个列表通过从所有单词中省略一个字母来排序。