java - 在我的 java 函数中实现搜索

Question

我需要一个java代码来选择两个单词之间的最短路径，每一步只改变一个字母。我想实现深度优先搜索；我认为这会解决我的问题。我正在阅读它，但我不知道如何实现它。有人可以帮助我吗？

Answer 1

我高估了评论中的一些问题限制；这其实是一个非常简单的BFS问题。 DFS不合适，因为它在探索靠近根节点的节点的邻居之前沿着每条路径一直到达终端节点。这意味着不能保证最短路径。另一方面，BFS 首先探索附近的节点，并保证最短路径。这个问题很好地说明了两种方法之间的差异。

您当前的实现是递归的，它使用调用堆栈作为 DFS 数据结构。由于堆栈是后进先出(LIFO)结构，当前节点的邻居将很快被埋在首先弹出和探索的邻居的邻居下面。

以下是使用队列(先进先出或 FIFO)将 find 方法实现为 BFS 的实现:

def find(start, target, words):
    alpha = [chr(x) for x in range(97, 123)]
    visited = {start: None}
    queue = [start]

    while queue:
        curr = queue.pop(0)

        if curr == target:
            path = []

            while curr:
                path.insert(0, curr)
                curr = visited[curr]

            return path

        letters = list(curr)

        for i, c in enumerate(letters):
            for letter in alpha:
                new_word = "".join(letters[:i]) + letter + "".join(letters[i+1:])

                if new_word in words and new_word not in visited:
                    visited[new_word] = curr
                    queue.append(new_word)


words = set([w.strip() for w in open("dictionary.txt").readlines()])
print(find("lead", "gold", words))
print(find("hide", "seek", words))

输出:

['lead', 'load', 'goad', 'gold']
['hide', 'bide', 'bids', 'beds', 'bees', 'sees', 'seek']

请注意，第二条路径与您的示例同样短，但使用不同的路线。如果需要，您可以轻松调整算法来计算所有最短路径。

相比之下，将队列更改为堆栈的简单修改(一个字符更改:pop(0) -> pop())向我们展示了 DFS 的结果:

['lead', 'leas', 'leys', 'lays', 'laws', 'lawn', 'lain', 'lair', 'wair', 'wait', 'watt', 'wats', 'wars', 'wary', 'wavy', 'wave', 'wane', 'wand', 'wynd', 'wyns', 'wyes', 'woes', 'wows', 'yows', 'yowl', 'yawl', 'yawp', 'yaup', 'yaud', 'yard', 'yarn', 'tarn', 'tart', 'taut', 'taus', 'tavs', 'vavs', 'vans', 'vang', 'yang', 'yank', 'yack', 'yuck', 'yuch', 'yech', 'yeah', 'year', 'wear', 'wean', 'ween', 'weet', 'west', 'wost', 'wort', 'worn', 'sorn', 'sori', 'soli', 'sols', 'soys', 'soya', 'soma', 'some', 'sone', 'song', 'sung', 'suns', 'suss', 'sass', 'sash', 'wash', 'wasp', 'wisp', 'wiss', 'wigs', 'zigs', 'zits', 'ziti', 'titi', 'tipi', 'tips', 'tins', 'tiny', 'tidy', 'tide', 'tire', 'tiro', 'tyro', 'typo', 'type', 'tyne', 'tune', 'tuna', 'tufa', 'tuft', 'toft', 'tofu', 'tolu', 'toll', 'tool', 'toon', 'town', 'towy', 'tory', 'tors', 'tots', 'tote', 'toke', 'take', 'taka', 'taxa', 'taxi', 'tali', 'talk', 'task', 'tusk', 'tush', 'tosh', 'toph', 'soph', 'soth', 'sith', 'site', 'size', 'bize', 'bise', 'bisk', 'birk', 'birr', 'bier', 'beer', 'bees', 'bets', 'beth', 'bath', 'bate', 'bare', 'barm', 'balm', 'bals', 'bams', 'bums', 'bump', 'burp', 'bury', 'busy', 'bust', 'butt', 'bott', 'bota', 'bora', 'mora', 'more', 'move', 'rove', 'roue', 'roux', 'doux', 'dour', 'dorr', 'dorp', 'gorp', 'goop', 'goos', 'gods', 'gids', 'gies', 'gien', 'girn', 'girt', 'gist', 'gast', 'vast', 'vase', 'vale', 'vole', 'volt', 'molt', 'moly', 'mopy', 'mops', 'moss', 'mosk', 'monk', 'mono', 'mozo', 'bozo', 'bolo', 'bold', 'gold']
['hide', 'hive', 'hove', 'howe', 'hows', 'hoys', 'hoya', 'hora', 'horn', 'hern', 'hers', 'hets', 'heth', 'hath', 'hate', 'haze', 'hazy', 'mazy', 'many', 'mans', 'mays', 'mayo', 'mako', 'make', 'mare', 'mart', 'maut', 'maun', 'mawn', 'mown', 'moon', 'moot', 'mott', 'mots', 'moss', 'mosk', 'monk', 'mono', 'mozo', 'bozo', 'boyo', 'toyo', 'toro', 'tory', 'towy', 'cowy', 'cowl', 'cool', 'coos', 'cops', 'cope', 'cote', 'cute', 'cuts', 'cuss', 'cusk', 'cask', 'cast', 'cant', 'cane', 'cave', 'cavy', 'caky', 'laky', 'lakh', 'lash', 'lass', 'laws', 'yaws', 'yawp', 'yaup', 'yaud', 'yard', 'yarn', 'warn', 'wary', 'waly', 'wall', 'wawl', 'pawl', 'pail', 'pair', 'parr', 'pars', 'pats', 'paty', 'pity', 'pith', 'pish', 'piss', 'pips', 'pipe', 'pine', 'pint', 'punt', 'puny', 'pony', 'pons', 'poms', 'pomp', 'poop', 'poor', 'pour', 'pout', 'post', 'pose', 'pore', 'pork', 'pock', 'poco', 'polo', 'poll', 'pull', 'puls', 'pugs', 'pugh', 'vugh', 'vugg', 'mugg', 'migg', 'migs', 'mirs', 'miry', 'airy', 'airt', 'girt', 'giro', 'gyro', 'gyre', 'gybe', 'gibe', 'gibs', 'gins', 'gink', 'gunk', 'guck', 'geck', 'geek', 'seek']

如您所见，这根本不是最短路径!