查找列表中仅相差一个字母的所有单词

Question

对于w列表中的任何给定单词words，我想找到列表中可以w通过更改其中的单个字母而变成的所有其他单词。所有的词都是等长的，只允许替换。调用这个函数parent(w)。

例如，给定words = ["hot","dot","dog","lot","log","cog"]，parent("cog")将是["dog", "log"]。parent("lot")会是["dot", "hot", "log"]等等

为此，我首先构建一个反向索引，其中的键映射到在索引处(str, int)具有字符的单词。然后，找到一个词的父词就变成了将所有与该词在相同位置具有相同字母的词相交的任务，除了一个。strint

代码如下，产生一个空集。为什么它不起作用？

from typing import Iterator, Dict, Tuple, Set

import itertools

graph: Dict[Tuple[str, int], Set[int]] = dict()

for i, word in enumerate(words):

    for j, ch in enumerate(word):

        if (ch, j) not in graph:

            graph[(ch, j)] = set()

        graph[(ch, j)].add(i)

def parents(word: str) -> Iterator[int]:

    n: int = len(word)

    s: Set[int] = set()

    for part in itertools.combinations(range(n), n - 1):

        keys = map(lambda x: (word[x], x), part)

        existing_keys = filter(lambda k: k in graph, keys)

        for y in itertools.chain(map(lambda k: graph[k], existing_keys)):

            s = s.intersection(set(y)) if s else set(y)

    return filter(lambda i: words[i] != word, s)

print(list(parents("cog"))) # empty!!!

Answer 1

您的解决方案几乎就绪。问题是您正在与找到的所有内容相交。但是您应该为每个组合附加结果。在你的第一个 for 循环中移动s: Set[int] = set()，并在第二个 for 循环之后附加你的结果，它就会起作用。是这样的：def parents(word: str) -> Set[int]:    ret: Set[int] = set()    for part in itertools.combinations(range(n), n - 1):        keys = map(lambda x: (word[x], x), part)        existing_keys = filter(lambda k: k in graph, keys)        s: Set[int] = set()        for y in map(lambda k: graph[k], existing_keys):            s = s.intersection(set(y)) if s else set(y)        ret.update(filter(lambda i: words[i] != word, s))    return ret

Answer 2

一个非常简单的解决方案。一种不同的方法。复杂性：O(N * 26) => O(N)- 其中 N 是每个单词中的字符数。def main(words, word):    words = set(words)    res = []    for i, _ in enumerate(word):        for c in 'abcdefghijklmnopqrstuvwxyz':            w = word[:i] + c + word[i+1:]            if w != word and w in words:                res.append(w)    return resprint(main(["hot","dot","dog","lot","log","cog"], "cog"))# ['dog', 'log']除了迭代所有字母表，您还可以选择仅迭代列表中出现的字母表，使用：{letter for w in words for letter in w}

Answer 3

Levenshtein 距离算法将实现您正在寻找的内容。from Levenshtein import distance  # pip install python-Levenshteinwords = ["hot", "dot", "dog", "lot", "log", "cog"]parent = 'cog'# find all words matching with one substitutionedits = [w for w in words if distance(parent, w) == 1]print(edits)输出：['dog', 'log']如果您不想安装任何库，可以使用该算法的 Python 实现提供很好的在线资源。

Answer 4

我会使用 Python in 函数检查父词 w 的每个字母与列表中的每个词。例如针对parent("cog")单词列表：["hot","dot","dog","lot","log","cog"]产量：[1, 1, 2, 1, 2, 3]数字 2 显示正确的单词：dog 和 log。