如何从列表中找到最短的公共子字符串？

Question

假设一个Python列表：

['ayiy', 'ayiya', 'ayiyas', 'back', 'backu', 'backup', 'backup-', 'backup1', 'backuph', 'backupm', 'backups', 'bakc', 'bakcu', 'bakcup', 'bakcup-', 'best', 'best-', 'best-b', 'best-ba', 'best-n', 'best-na', 'bili', 'biliy', 'biliyi', 'biliyil', 'bith', 'bithu', 'bithun', 'bithunt', 'blac', 'black', 'blackh', 'blackho', 'boos', 'boost', 'boost-', 'boost-s', 'boost-y', 'bout', 'bouth', 'bouths', 'bugs', 'bugsb', 'bugsbu', 'bugsbun']

生成一组唯一子字符串的最佳方法是什么？（至少3个字符，但如果不是最短的相似子字符串，则更多字符）：

['ayi', 'bac', 'bak', 'bes', 'bil', 'bit', 'blac', 'boo', 'bou', 'bug']

Answer 1

您可以这样做以获得3个字母子字符串的完整列表

your_list = ['ayiy', 'ayiya', 'ayiyas', 'back', 'backu', 'backup', 'backup-', 'backup1', 'backuph', 'backupm', 'backups', 'bakc', 'bakcu', 'bakcup', 'bakcup-', 'best', 'best-', 'best-b', 'best-ba', 'best-n', 'best-na', 'bili', 'biliy', 'biliyi', 'biliyil', 'bith', 'bithu', 'bithun', 'bithunt', 'blac', 'black', 'blackh', 'blackho', 'boos', 'boost', 'boost-', 'boost-s', 'boost-y', 'bout', 'bouth', 'bouths', 'bugs', 'bugsb', 'bugsbu', 'bugsbun']

smallest_list = [x[:3] for x in your_list]

unique_list = [x for x in set(smallest_list) if smallest_list.count(x) > 1]

unique_list.sort()

print (unique_list)

输出将是：

['ayi', 'bac', 'bak', 'bes', 'bil', 'bit', 'bla', 'boo', 'bou', 'bug']

注意：此答案仅给出您发布的结果。如果您要从原始列表中查找所有唯一的3个字符子字符串，则还有更多。例如：yiy、iya、ack、kup以及更多是可以满足条件的3个字母子字符串的一部分。如果你想要一个解决方案，那么答案将是不同的

要获取完整的3字符列表（其中3字符字符串多次出现），请使用以下代码：

full_3char_list = [xa[i:i+3] for xa in your_list for i in range(len(xa)-2)]

unique_3char_list = [x for x in set(full_3char_list) if full_3char_list.count(x) > 1]

unique_3char_list.sort()

print (unique_3char_list)

输出将是：

['ack', 'akc', 'ayi', 'bac', 'bak', 'bes', 'bil', 'bit', 'bla', 'boo', 'bou', 'bug', 'ckh', 'cku', 'cup', 'est', 'gsb', 'hun', 'ili', 'ith', 'iya', 'iyi', 'kcu', 'kup', 'lac', 'liy', 'oos', 'ost', 'out', 'sbu', 'st-', 't-b', 't-n', 'thu', 'ugs', 'up-', 'uth', 'yiy']

如果您想要所有3个字符字符串的唯一列表，那么您可以在完整的字符列表上进行设置

unique_3char_full_list = sorted(list(set(full_3char_list)))
print (unique_3char_full_list)

['-ba', '-na', 'ack', 'akc', 'ayi', 'bac', 'bak', 'bes', 'bil', 'bit', 'bla', 'boo', 'bou', 'bug', 'bun', 'ckh', 'cku', 'cup', 'est', 'gsb', 'hun', 'ili', 'ith', 'iya', 'iyi', 'kcu', 'kho', 'kup', 'lac', 'liy', 'oos', 'ost', 'out', 'sbu', 'st-', 't-b', 't-n', 't-s', 't-y', 'ths', 'thu', 'ugs', 'unt', 'up-', 'up1', 'uph', 'upm', 'ups', 'uth', 'yas', 'yil', 'yiy']