對于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, Setimport itertoolsgraph: 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!!!
4 回答
森林海
TA貢獻2011條經驗 獲得超2個贊
您的解決方案幾乎就緒。問題是您正在與找到的所有內容相交。但是您應該為每個組合附加結果。在你的第一個 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
繁星點點滴滴
TA貢獻1803條經驗 獲得超3個贊
一個非常簡單的解決方案。一種不同的方法。
復雜性：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}
慕運維8079593
TA貢獻1876條經驗 獲得超5個贊
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 實現提供很好的在線資源。
撒科打諢
TA貢獻1934條經驗 獲得超2個贊
我會使用 Python in 函數檢查父詞 w 的每個字母與列表中的每個詞。
例如針對parent("cog")單詞列表：
["hot","dot","dog","lot","log","cog"]
產量：
[1, 1, 2, 1, 2, 3]
數字 2 顯示正確的單詞：dog 和 log。
添加回答
舉報
0/150
提交
取消