查找列表中所有相差一个字母的单词 [英] Find all the words in the list that differ by a single letter

问题描述

对于列表words中的任何给定单词w，我想在列表中找到所有其他单词，只需更改其中的单个字母即可成为w.所有单词的长度相等，并且仅允许替换.调用此功能parent(w).

For any given word w in a list words, I want to find all the other words in the list that can become w by changing a single letter in them. All words are of equal length, and only substitution is allowed. Call this function parent(w).

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

For example, given words = ["hot","dot","dog","lot","log","cog"], parent("cog") would be ["dog", "log"]. parent("lot") would be ["dot", "hot", "log"] etc.

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

To do this, I first build a reverse index where the keys (str, int) map to the words that have character str at index int. Then, finding the parents of a word becomes the task of intersecting all the words that have the same letters as the word in the same positions, except for one.

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

The code is as follows, which produces an empty set. Why is it not working?

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!!!

推荐答案

一个非常简单的解决方案.一种不同的方法.

A very simple solution. A different approach.

复杂度:O(N * 26) => O(N)-其中N是每个单词中的字符数.

Complexity: O(N * 26) => O(N) - where N is the number of characters in each word.

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 res


print(main(["hot","dot","dog","lot","log","cog"], "cog"))
# ['dog', 'log']

---

除了遍历所有字母之外，您还可以选择仅遍历列表中出现的字母，方法是:

---

Instead of iterating over all the alphabets, you can also choose to only iterate on the alphabets that are occurring in the list using:

{letter for w in words for letter in w}

这篇关于查找列表中所有相差一个字母的单词的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！