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

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']

标签： pythonpython-3.x

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 char 列表（其中 3 char 字符串出现多次），请使用以下代码：

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 个字符字符串的唯一列表，那么你可以在 full_3char_list 上做一个集合。

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']