목록에서 한 글자가 다른 모든 단어 찾기

Question

w목록의 특정 단어 에 대해 목록 words에서 w단일 문자를 변경하여 될 수있는 다른 모든 단어를 찾고 싶습니다 . 모든 단어의 길이가 같으며 대체 만 허용됩니다. 이 함수를 호출하십시오 parent(w).

예를 들어, 주어진 words = ["hot","dot","dog","lot","log","cog"], parent("cog")될 것이다 ["dog", "log"]. 등 parent("lot")이 될 것입니다 ["dot", "hot", "log"].

이를 위해 먼저 index에 (str, int)문자가있는 단어에 키가 매핑 되는 역 색인 str을 작성 int합니다. 그런 다음 단어의 부모를 찾는 것은 같은 위치에있는 단어와 같은 글자를 가진 모든 단어를 교차하는 작업이됩니다.

코드는 다음과 같으며 빈 집합을 생성합니다. 왜 작동하지 않습니까?

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

매우 간단한 솔루션입니다. 다른 접근 방식.

복잡성 : 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}

Answer 2

솔루션이 거의 완료되었습니다. 문제는 당신이 찾은 모든 것을 교차 시키고 있다는 것 입니다. 그러나 대신 각 조합에 대한 결과를 추가해야합니다. s: Set[int] = set()첫 번째 for 루프 내부로 이동 하고 두 번째 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 3

Levenshtein 거리 알고리즘은 원하는 것을 얻을 수 있습니다.

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 구현에 대한 좋은 온라인 리소스 가 있습니다.

Answer 4

Python in 함수를 사용하여 목록의 각 단어에 대해 부모 단어 w의 모든 문자를 확인합니다.

예를 들어 parent("cog"), 단어 목록에 대해 :

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

수율 :

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

숫자 2는 올바른 단어 인 개와 통나무를 보여줍니다.