對(duì)于w列表中的任何給定單詞words，我想找到列表中可以w通過更改其中的單個(gè)字母而變成的所有其他單詞。所有的詞都是等長的，只允許替換。調(diào)用這個(gè)函數(shù)parent(w)。例如，給定words = ["hot","dot","dog","lot","log","cog"]，parent("cog")將是["dog", "log"]。parent("lot")會(huì)是["dot", "hot", "log"]等等為此，我首先構(gòu)建一個(gè)反向索引，其中的鍵映射到在索引處(str, int)具有字符的單詞。然后，找到一個(gè)詞的父詞就變成了將所有與該詞在相同位置具有相同字母的詞相交的任務(wù)，除了一個(gè)。strint代碼如下，產(chǎn)生一個(gè)空集。為什么它不起作用？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貢獻(xiàn)2011條經(jīng)驗(yàn) 獲得超2個(gè)贊
您的解決方案幾乎就緒。問題是您正在與找到的所有內(nèi)容相交。但是您應(yīng)該為每個(gè)組合附加結(jié)果。在你的第一個(gè) for 循環(huán)中移動(dòng)s: Set[int] = set()，并在第二個(gè) for 循環(huán)之后附加你的結(jié)果，它就會(huì)起作用。是這樣的：
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
繁星點(diǎn)點(diǎn)滴滴
TA貢獻(xiàn)1803條經(jīng)驗(yàn) 獲得超3個(gè)贊
一個(gè)非常簡單的解決方案。一種不同的方法。
復(fù)雜性：O(N * 26) => O(N)- 其中 N 是每個(gè)單詞中的字符數(shù)。
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']
除了迭代所有字母表，您還可以選擇僅迭代列表中出現(xiàn)的字母表，使用：
{letter for w in words for letter in w}
慕運(yùn)維8079593
TA貢獻(xiàn)1876條經(jīng)驗(yàn) 獲得超5個(gè)贊
Levenshtein 距離算法將實(shí)現(xiàn)您正在尋找的內(nèi)容。
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 實(shí)現(xiàn)提供很好的在線資源。
撒科打諢
TA貢獻(xiàn)1934條經(jīng)驗(yàn) 獲得超2個(gè)贊
我會(huì)使用 Python in 函數(shù)檢查父詞 w 的每個(gè)字母與列表中的每個(gè)詞。
例如針對(duì)parent("cog")單詞列表：
["hot","dot","dog","lot","log","cog"]
產(chǎn)量：
[1, 1, 2, 1, 2, 3]
數(shù)字 2 顯示正確的單詞：dog 和 log。
添加回答
舉報(bào)
0/150
提交
取消