python - 优化字梯

我想解决这个问题：
给出两个单词（beginWord和endWord）和字典的单词表，
求从beginWord到
结束语，这样：
一次只能更改一个字母每个转换的单词必须
存在于单词列表中。注意beginword不是一个转换的单词。
注：
如果没有这样的转换序列，则返回0。所有单词都有
同样的长度所有单词只包含小写字母
角色。您可以假定单词列表中没有重复的单词你可以
假设beginword和endword不为空且不相同。
https://leetcode.com/problems/word-ladder/
我正确的工作代码：

from collections import Counter, defaultdict, deque
def can_change(x, y):
    diff = 0
    for u, v in zip(x, y):
        if u != v:
            diff += 1
        if diff>1:
            return False
    return diff == 1


class Solution:
    def ladderLength(self, start, end, dict):
        graph = defaultdict(list)
        words = set(dict+[start])
        for w1 in words:
            for w2 in words:
                if w1 != w2:
                    if can_change(w1, w2):
                        graph[w1].append(w2)
        def bfs(node):
            queue = deque([(node, 1)])
            seen = {node}
            while queue:
                node, count = queue.pop()
                if node == end:
                    return count
                for neb in graph[node]:
                    if neb not in seen:
                        seen.add(neb)
                        queue.appendleft((neb, count+1))
            return 0
        return bfs(start)

这在大型测试用例中是过时的如何在时间复杂度上进行优化？

最佳答案

我尽量避免使用邻接列表显式地定义图——我认为这是多余的。
相反，您可以尝试隐式运行bfs。
伪代码：

Q = empty queue
beginWord.depth = 0
Q.enqueue(beginWord)
while  Q is not empty:
    w = Q.dequeue
    for l in dictionary:
        if l is a one char transform on w:
              if l == endWord:
                  return w.depth+1
              else:
                  l.depth = w + 1
                  Q.enqueue(l)
                  remove l from the dictionary.
return 0

我想这个方法和你用的BFS方法很相似它以BFS的方式扫描“图形”，跟踪从一开始就可以找到的单词，以及当前的搜索深度如果它找到了词尾，就返回它的深度。
这里的主要区别是我们不创建一个图表来建模整个字典我们确实会扫描广度优先的样式搜索，但我们会避免跟踪稍后不使用的信息，例如路径上的边缘、无法访问的单词等。
这里的渐近运行时间是o（nx），x是从beginword可以到达的单词数。在最坏的情况下，它不会超过你的算法，但在许多其他情况下，它会超过你的算法。
它还为您保存了在构建图之后必须执行的BFS搜索，并从列表中取出已被证明可以访问的单词，从而减少常量。

关于python - 优化字梯，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58626761/