リスト内で1文字異なるすべての単語を検索します

Aug 21 2020

wリスト内の任意の単語について、1文字を変更するwordsことでリスト内の他のすべての単語を検索したいと思いwます。すべての単語は同じ長さであり、置換のみが許可されます。この関数を呼び出しますparent(w)

たとえば、が与えられたwords = ["hot","dot","dog","lot","log","cog"]場合、parent("cog")はになります["dog", "log"]。などにparent("lot")なります["dot", "hot", "log"]

これを行うには、最初に、キーがインデックスに(str, int)文字を持つ単語にマップされる逆インデックスを作成strしますint。次に、単語の親を見つけることは、1つを除いて、同じ位置にある単語と同じ文字を持つすべての単語を交差させるタスクになります。

コードは次のとおりで、空のセットが生成されます。なぜ機能しないのですか?

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

回答

1 HarshalParekh Aug 21 2020 at 23:27

非常に簡単な解決策。別のアプローチ。

複雑さ: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 res


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

すべてのアルファベットを反復処理する代わりに、次を使用して、リストで発生しているアルファベットのみを反復処理することもできます。

{letter for w in words for letter in w}
2 ahelium Aug 21 2020 at 23:26

あなたの解決策はほとんどあります。問題は、見つけたものすべてと交差していることです。ただし、代わりに、組み合わせごとに結果を追加する必要があります。s: Set[int] = set()最初のforループ内に移動し、2番目の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
1 thorntonc Aug 21 2020 at 23:14

レーベンシュタイン距離アルゴリズムは、あなたが探しているものを実現します。

from Levenshtein import distance  # pip install python-Levenshtein

words = ["hot", "dot", "dog", "lot", "log", "cog"]
parent = 'cog'
# find all words matching with one substitution
edits = [w for w in words if distance(parent, w) == 1]
print(edits)

出力:

['dog', 'log']

ライブラリをインストールしたくない場合は、アルゴリズムのPython実装に関する優れたオンラインリソースがあります。

JorgeRueda Aug 22 2020 at 00:36

Python in関数を使用して、親単語wのすべての文字をリストの各単語と照合します。

たとえばparent("cog")、単語のリストに対して:

["hot","dot","dog","lot","log","cog"]

収量:

[1, 1, 2, 1, 2, 3]

番号2は正しい単語を示しています:犬と丸太。