通过有效单词将一个单词转换为另一个单词的算法

# Given two words of equal length that are in a dictionary, write a method to transform one word into another word by changing only
# one letter at a time.  The new word you get in each step must be in the
# dictionary.

# def transform(english_words, start, end):

# transform(english_words, 'damp', 'like')
# ['damp', 'lamp', 'limp', 'lime', 'like']
# ['damp', 'camp', 'came', 'lame', 'lime', 'like']


def is_diff_one(str1, str2):
    if len(str1) != len(str2):
        return False

    count = 0
    for i in range(0, len(str1)):
        if str1[i] != str2[i]:
            count = count + 1

    if count == 1:
        return True

    return False


potential_ans = []


def transform(english_words, start, end, count):
    global potential_ans
    if count == 0:
        count = count + 1
        potential_ans = [start]

    if start == end:
        print potential_ans
        return potential_ans

    for w in english_words:
        if is_diff_one(w, start) and w not in potential_ans:
            potential_ans.append(w)
            transform(english_words, w, end, count)
            potential_ans[:-1]

    return None


english_words = set(['damp', 'camp', 'came', 'lame', 'lime', 'like'])
transform(english_words, 'damp', 'lame', 0)

#1 楼

始终返回答案

无论何时编写算法，它都应返回答案。不打印并返回，而不仅仅是打印。刚回来。如果要打印，可以随时输入print some_algo(...)。

is_diff_one

我们可以写得更干净一些。 Python标准库中有一个zip()函数，该函数可以一次遍历多个可迭代对象。 （在Python 2.7中，我们应该使用itertools.izip()，因为这样不会预先生成整个列表）。这样做的好处是我们可以编写：

count = 0
for a, b in zip(str1, str2):
    if a != b:
        count += 1
        if count > 1:
            # quit early
            return False

# in case we're equal
return count == 1

尽量避免使用以下模式：

if expr:
    return True
return False

与return expr

回溯

此行相同：

potential_ans[:-1]

实际上不执行任何操作。它将返回一片potential_ans，但实际上并没有对其进行修改。您想做的是

potential_ans.pop()

但这很容易出错（并且依赖于全局状态）。无需修改potential_ans，我们可以做的是为每个递归实例提供一个新对象。这使我想到...

您的算法

现在，您希望它完全独立。您想避免使用全局变量是正确的-而且您有大多数正确的想法，因为我们要递归地调用下一个单词。一个变化是最后一个参数。 count在这里并不是很有意义。相反，您想要的是您到目前为止所走的道路：

def transform(english_words, start, end, cur_path):
    if start == end:
        return [cur_path]

这样，我们的道路是本地的，而不是全局的。然后，当您在执行操作时，我们只剩下其余的单词：

results = []
for w in english_words:
    if is_diff_one(w, start) and w not in cur_path:
        solutions = transform(english_words, w, end, cur_path + [w])
        results.extend(solutions)
return results

请注意，我正在将您的返回类型从列表更改为列表列表。现在，这将返回所有可能的转换列表的列表。

当然，我们需要一个明智的默认值cur_path。让我们避免用户提出一个：

def transform(english_words, start, end, cur_path=None):
    if cur_path is None:
        cur_path = [start]

#2 楼

这里还有其他四个答案，它们都有非常明智的建议。但是据我所知，它们都没有指出所选算法的可怕的运行时复杂性，因此我认为有必要提供额外的答案。

1。错误

>>> english_words = set('bar bat cat war'.split())
>>> transform(english_words, 'bar', 'war', 0)
['bar', 'bat', 'cat', 'war']

正如Barry所指出的，这是因为行

potential_ans[:-1]

是错误的：

potential_ans.pop()

接下来，我将假定该错误已修复。

2。抽象问题

这里要解决的问题可以看作是图上的一个问题，其中每个单词都是图的一个节点，如果两个单词相差一个字母，则两个单词相连。假设单词是cake，compe，camp，dame，dum，dike，dime，lake，lame，lamp，like，lime和limp，则图形如下所示：



一个单词到另一个单词的转换对应于该图中的路径。例如，蛋糕到li行的一种可能转换对应于此处突出显示的路径：



查找两个单词之间的最短转换对应于找到两个节点之间的最短路径在图形中。

用图形之类的抽象数据结构来思考问题有很多好处，包括：


有用于描述的标准术语问题：这里是节点，边，路径。
有支持有效操作的数据结构的具体表示。
您可以查找解决问题的最知名算法，而不必发明自己的算法。自己的。

3。算法的描述和复杂性

解决了§1中指出的错误，程序要做的就是在start开头的词图中生成所有简单路径（无重复节点的路径），直到它会找到通往end的路径。

但这可能会花费非常长的时间：

>>> from timeit import timeit
>>> english_words = set('bar bat cat eat fat hat mat oat pat rat sat tat vat war'.split())
>>> timeit(lambda:transform(english_words, 'bar', 'war', 0), number=1)
['bar', 'war']
2732.44891167

为什么该算法需要四分之三小时才能找到此结果？好吧，正在搜索的图形如下所示：



该算法从bar开始，并不断向其路径添加节点，直到不重复任何操作都无法继续节点。例如（取决于从set检索单词的顺序），它可能最终使用以下路径：



回溯几步后，它将找到以下路径：



等等。您将看到它会探索从bar开始的所有路径-击球，然后访问所有路径。有\ $ 11！ = 39,916,800 \ $这样的路径，只有在探索了所有路径后，才会考虑路径栏-战争。

检查带有\ $ m \ $字母的两个单词是否相差一个字母时间\ $ O（m）\ $，因此，如果每个\ $ n \ $个单词的\ $ m \ $个字母，则总运行时间为\ $ O（n！m）\ $。

4。更好的算法

如果使用标准的图搜索算法之一（例如Dijkstra或A *），则可能会做得更好。这是使用后者的一种实现。

from collections import defaultdict, namedtuple
from heapq import heappush, heappop

class NotFound(Exception):
    pass

def word_ladder(words, start, end):
    """Return a word ladder (a list of words each of which differs from
    the last by one letter) linking start and end, using the given
    collection of words. Raise NotFound if there is no ladder.

    >>> words = 'card care cold cord core ward warm'.split()
    >>> ' '.join(word_ladder(words, 'cold', 'warm'))
    'cold cord card ward warm'

    """
    # Find the neighbourhood of each word.
    placeholder = object()
    matches = defaultdict(list)
    neighbours = defaultdict(list)
    for word in words:
        for i in range(len(word)):
            pattern = tuple(placeholder if i == j else c
                            for j, c in enumerate(word))
            m = matches[pattern]
            m.append(word)
            neighbours[word].append(m)

    # A* algorithm: see https://en.wikipedia.org/wiki/A*_search_algorithm

    # Admissible estimate of the steps to get from word to end.
    def h_score(word):
        return sum(a != b for a, b in zip(word, end))

    # Closed set: of words visited in the search.
    closed_set = set()

    # Open set: search nodes that have been found but not yet
    # processed. Accompanied by a min-heap of 4-tuples (f-score,
    # g-score, word, previous-node) so that we can efficiently find
    # the node with the smallest f-score.
    Node = namedtuple('Node', 'f g word previous')
    open_set = set([start])
    open_heap = [Node(h_score(start), 0, start, None)]
    while open_heap:
        node = heappop(open_heap)
        if node.word == end:
            result = []
            while node:
                result.append(node.word)
                node = node.previous
            return result[::-1]
        open_set.remove(node.word)
        closed_set.add(node.word)
        g = node.g + 1
        for neighbourhood in neighbours[node.word]:
            for w in neighbourhood:
                if w not in closed_set and w not in open_set:
                    next_node = Node(h_score(w) + g, g, w, node)
                    heappush(open_heap, next_node)
                    open_set.add(w)

    raise NotFound("No ladder from {} to {}".format(start, end))

假设存在\ $ m \ $个字母的\ $ n \ $个单词，而其中的\ $ e \ $个边单词图。然后此算法使用\ $ O（m ^ 2n）\ $查找边缘，然后使用\ $ O（e + mn + n \ log n）\ $查找最短路径。

因此这样可以在合理的时间内找到大型单词上最短的阶梯：

>>> dictionary = [w.strip() for w in open('/usr/share/dict/words') if w == w.lower()]
>>> five_letter_words = [w for w in dictionary if len(w) == 5]
>>> len(five_letter_words)
8497
>>> from timeit import timeit
>>> timeit(lambda:print(' '.join(word_ladder(five_letter_words, 'above', 'below'))), number=1)
above amove amoke smoke smoky sooky booky booly bolly bally balli balai balao baloo balow below
0.3188382713124156

#3 楼

is_diff_one()

您已选择要求两个字符串的长度相同。很好，但是也许您也想考虑添加或删除一个字母与一个字母的区别。

编写此函数的更简单方法是

def is_diff_one(str1, str2):
    return 1 == sum(c1 != c2 for c1, c2 in zip(str1, str2))

缺点是一旦发现第二个区别就不会短路。对于像测试用例这样的简短单词，我认为这并不重要。

递归和回溯

potential_ans[:-1]无效。它产生并丢弃potential_ans的副本，省略最后一个元素。您可能想要potential_ans.pop()。

，但是如果您仍然对如何传递数据感到困惑，那不是我建议做回溯的方式。好的选择是：


正确使用递归，并将所需的所有状态信息存储在调用堆栈中，或者
使用自己的list作为堆栈，在在这种情况下，我建议循环而不是递归。

选项2实施起来比较棘手，因此我建议您坚持使用递归方法。

递归

进行递归时，不应将函数视为具有副作用的过程。而是从数学意义上将它们视为函数：该函数必须仅根据其参数产生一个确定性答案，并且不会产生副作用。

def transform(dictionary, goal, chain):
    if chain[-1] == goal:
        return chain
    for word in dictionary:
        if is_diff_one(word, chain[-1]) and word not in chain:
            result = transform(dictionary, goal, chain + [neighbor])
            if result:
                return result

print transform(english_words, 'lame', ['damp'])

您可以通过使用append()和pop()来提高效率，但是您应该确保完全了解如何正确执行递归，然后再对此类突变操作感到困惑，因为它们具有副作用。

我已经删除了count参数，因为它只是初始化链的繁琐方式。

#4 楼

我将集中精力实现递归。

首先，让我们避免使用全局变量。最简单的方法是保持相同的结构，但将其移入本地名称空间：

def transform(english_words, start, end):
    potential_ans = [start]
    results = []
    def recursion(start_, end_):
        if start_ == end_:
            results.append(list(potential_ans))
            return
        for w in english_words:
            if is_diff_one(w, start_) and w not in potential_ans:
                potential_ans.append(w)
                recursion(w, end_)
                potential_ans.pop()
    recursion(start, end)
    return results

english_words = set(['damp', 'camp', 'came', 'dame', 'lame', 'lime', 'like'])
for answer in transform(english_words, 'damp', 'lame'):
    print(answer)

我主要是使transform一个函数可以设置正确的数组，然后将原始实现转换为嵌套函数recursion。注意，我已经创建了一个用于存储结果的results数组。还请注意，存储结果时需要复制潜在答案，因为我们将继续修改potential_ans。

我还修改了单词列表，因此不只一个结果。

我想你想获得所有答案；发现答案后，应该不难修改它以结束递归...但是，下面将描述一种更好的方法。

鉴于此更改，recursion的参数为冗余：可以更改为以下内容。 （如果您真的很认真，则应该分析此更改，以确定它是否确实使事情变得更快）。

def transform(english_words, start, end):
    potential_ans = [start]
    results = []
    def recursion():
        tail = potential_ans[-1]
        if potential_ans[-1] == end:
            results.append(list(potential_ans))
            return
        for w in english_words:
            if is_diff_one(w, tail) and w not in potential_ans:
                potential_ans.append(w)
                recursion()
                potential_ans.pop()
    recursion()
    return results

现在，生成序列的更好的方法结果是使用发生器：

def transform(english_words, start, end):
    potential_ans = [start]
    def recursion():
        tail = potential_ans[-1]
        if potential_ans[-1] == end:
            yield list(potential_ans)
            return
        for w in english_words:
            if is_diff_one(w, tail) and w not in potential_ans:
                potential_ans.append(w)
                yield from recursion()
                potential_ans.pop()
    yield from recursion()

english_words = set(['damp', 'camp', 'came', 'dame', 'lame', 'lime', 'like'])
for answer in transform(english_words, 'damp', 'lame'):
    print(answer)

请注意使用yield和yield from产生结果。使用生成器具有许多优点，包括：您可以在创建结果时看到它们，可以在对结果满意时停止迭代，而不必等待整个递归完成，而不必浪费时间内存/时间创建所有结果的列表。

生成器需要一点时间来习惯，但它们是值得的，并且通常应该优先于返回结果列表。

最后，最后一个巧妙的把戏； “进行更改...执行操作...撤消更改”的一般模式可能容易出错；很容易忘记撤消更改，或者使用奇数代码路径（例如，异常）跳过更改。

其他答案则建议复印。但是，这样的回溯算法通常会因这种更改而遭受严重的性能损失，因此，值得一提的是，无需引入副本即可缓解此问题的模式。

我们可以使用上下文管理器自动执行此操作，如下面。 （本篇文章无意成为上下文管理器的教程）

from contextlib import contextmanager

def transform(english_words, start, end):
    potential_ans = [start]

    @contextmanager
    def push(word):
        potential_ans.append(word)
        yield
        potential_ans.pop()

    def recursion():
        tail = potential_ans[-1]
        if potential_ans[-1] == end:
            yield list(potential_ans)
            return
        for w in english_words:
            if is_diff_one(w, tail) and w not in potential_ans:
                with push(w):
                    yield from recursion()
    yield from recursion()

最后，人们可能会不喜欢这样的事实，即有用的功能被嵌入在嵌套函数中；我们可以拉出嵌套函数：

@contextmanager
def temp_push(seq, ele):
    seq.append(ele)
    yield
    seq.pop()

def transform_recursion(english_words, end, potential_ans):
    tail = potential_ans[-1]
    if potential_ans[-1] == end:
        yield list(potential_ans)
        return
    for w in english_words:
        if is_diff_one(w, tail) and w not in potential_ans:
            with temp_push(potential_ans, w):
                yield from transform_recursion(english_words, end, potential_ans)


def transform(english_words, start, end):
    yield from transform_recursion(english_words, end, [start])

#5 楼

Proviso我还没有检查过代码的逻辑，主要只是检查了您可能曾经使用但错过的样式和语言功能。

使函数一次性使用

这是编程的一般规则，但是我发现一个在Python中强制执行的规则特别好，特别是因为很多小的，一次性使用的函数当您以PEP风格编写功能时，这些功能看起来非常漂亮（我很不擅长）。所以我不确定为什么要在transform中进行打印。通常，您应该尝试将日志记录保留为自己的功能，与计算等分开。在您打印结果然后返回结果的函数中尤其如此。为什么不返回然后打印返回的位置，以使代码更易于维护和理解？

很容易避免在Python中使用全局变量。

您提到您没有想要使用全局变量。不用了每当您担心操作全局变量时，都可以将变量传递给函数。如果可以避免，您不希望函数以任何方式依赖于全局名称。有很多方法可以解决此问题。一种是将全局变量包装在某种明智的类对象中。另外，作为补充，您应该将所有内容都作为参数传递给函数，即使它是全局的，也可以执行以下操作：

def transform(english_words, start, end, count, potential_ans):

Python是传递类似参考的内容，因此对potential_ans所做的更改将继续存在，至少在您执行诸如添加字母之类的操作时。在这篇SO帖子中了解更多有关此内容的信息。

效率

好像您经历的english_words比您需要的更多。找到所需的匹配项后，为什么不中断for loop？

关于效率，我建议在计数检查后再执行start == end检查。

如果您使用Python的一个不错的功能if count == 0是一个假值，则可以完全消除[]步骤。然后，您可以首先传递一个空列表，然后使用递归调用进行构建。将potential_ans作为参数传递后，首先传递一个空列表，然后使用以下语句：

potential_ans = potential_ans or [start]

这样可能会更有效（易于测试），并且它肯定比您现在使用的count检查更清晰，更简洁。

您的代码部分令人困惑

count在transform中做什么？我看到您有时在transform中增加它，并且在is_diff_one中也使用它。作为您的代码阅读者，我希望您评论count是否相关...这是一些时髦的全局变量操作还是仅仅是您喜欢的count变量名？这正是评论可以为您的读者节省大量工作的地方。

实际上，为什么在函数中重新定义potential_ans时将其设置为全局变量？为什么不直接自己初始化并继续将其作为参数传递（请参见上文）。这是一项设计决定，因此您应在此处发表评论，以向您感到困惑的读者解释。

for loop相对于english_words的最后一个表达式的意义是什么：potential_ans[:-1]。这真的让我感到困惑。你要改变什么吗？就我所了解的Python语法而言，您只是在引用此列表的最后一个元素，而不对此做任何事情。我想念什么吗？如果是这样，在这里发表评论会有所帮助。如果不是，则应将其删除，因为它除了运行不必要的表达式外根本不会影响程序。