我有一个名字和一个名字列表。我可以保证所选名称包含在其他名称列表中。
我想生成所选名称的最短子字符串,该子字符串仅包含在该名称中,而不包含在数据中的任何其他名称中。
>>> names = ['smith','jones','williams','brown','wilson','taylor','johnson','white','martin','anderson']
>>> find_substring('smith', names)
"sm"
>>> find_substring('williams', names)
"ll"
>>> find_substring('taylor', names)
"y"
我可以很容易地通过暴力破解这一点,方法是获取所选名称的第一个字母并查看它是否与任何名称匹配,然后迭代其余字母,然后是字母对,等等。
我的问题是我的列表包含一万多个名字,而且它们相当长 - 更类似于书名。暴力破解会永远。
是否有一些简单的方法可以有效地实现这一目标?
最佳答案
我相信你最好的选择是蛮力,但是,保留一个检查过的字母组合的字典以及它们是否与任何其他名称匹配。
["s":true, "m": true, "sm": false"]
首先查阅此列表将有助于减少检查其他字符串的代码并加快方法的运行速度。
关于python - 寻找最短的唯一子串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60022689/