我有一个字符串
s = "mouse"
和字符串列表
sub_strings = ["m", "o", "se", "e"]
我需要找出什么是sub_strings最好的和最短的匹配子集匹配是清单。 做这个的最好方式是什么？ 理想的结果将是[“M”，“O”，“SE”]因为他们一起拼莫斯
Answer 1:
您可以使用正则表达式：
import re
def matches(s, sub_strings):
sub_strings = sorted(sub_strings, key=len, reverse=True)
pattern = '|'.join(re.escape(substr) for substr in sub_strings)
return re.findall(pattern, s)
这至少是短而快，但它并不一定能找到匹配的最佳设置; 实在是太贪婪。 例如，
matches("bears", ["bea", "be", "ars"])
返回["bea"] ，当它应该返回["be", "ars"] 。
代码的说明：
第一行按长度排序的子串，使最长的字符串出现在列表的开始。 这确保了正则表达式将会倾向于更长的匹配在较短的。
第二行创建一个正则表达式模式包括所有的子串，由分离
|符号，这意味着“或”。第三行只是使用
re.findall功能找到在给定的字符串模式的所有比赛s。
Answer 2:
import difflib
print difflib.get_close_matches(target_word,list_of_possibles)
但不幸的是它不会对你的工作，例如上面你可以使用编辑距离，而不是...
def levenshtein_distance(first, second):
"""Find the Levenshtein distance between two strings."""
if len(first) > len(second):
first, second = second, first
if len(second) == 0:
return len(first)
first_length = len(first) + 1
second_length = len(second) + 1
distance_matrix = [[0] * second_length for x in range(first_length)]
for i in range(first_length):
distance_matrix[i][0] = i
for j in range(second_length):
distance_matrix[0][j]=j
for i in xrange(1, first_length):
for j in range(1, second_length):
deletion = distance_matrix[i-1][j] + 1
insertion = distance_matrix[i][j-1] + 1
substitution = distance_matrix[i-1][j-1]
if first[i-1] != second[j-1]:
substitution += 1
distance_matrix[i][j] = min(insertion, deletion, substitution)
return distance_matrix[first_length-1][second_length-1]
sub_strings = ["mo", "m,", "o", "se", "e"]
s="mouse"
print sorted(sub_strings,key = lambda x:levenshtein_distance(x,s))[0]
这将永远给你的“最接近”二字来你的目标（为最近的一些定义）
HTTP：//www.korokithakis.net/posts/finding-the-levenshtein-distance-in-python/莱文斯坦功能被盗
Answer 3:
该解决方案是基于此答案由用户野兽 。 它采用了acora包斯特凡Behnel高效地找到使用对象的子串的所有比赛阿霍Corasick算法 ，然后使用动态编程来找到答案。
import acora
import collections
def best_match(target, substrings):
"""
Find the best way to cover the string `target` by non-overlapping
matches with strings taken from `substrings`. Return the best
match as a list of substrings in order. (The best match is one
that covers the largest number of characters in `target`, and
among all such matches, the one using the fewest substrings.)
>>> best_match('mouse', ['mo', 'ou', 'us', 'se'])
['mo', 'us']
>>> best_match('aaaaaaa', ['aa', 'aaa'])
['aaa', 'aa', 'aa']
>>> best_match('abracadabra', ['bra', 'cad', 'dab'])
['bra', 'cad', 'bra']
"""
# Find all occurrences of the substrings in target and store them
# in a dictionary by their position.
ac = acora.AcoraBuilder(*substrings).build()
matches = collections.defaultdict(set)
for match, pos in ac.finditer(target):
matches[pos].add(match)
n = len(target)
# Array giving the best (score, list of matches) found so far, for
# each initial substring of the target.
best = [(0, []) for _ in xrange(n + 1)]
for i in xrange(n):
bi = best[i]
bj = best[i + 1]
if bi[0] > bj[0] or bi[0] == bj[0] and len(bi[1]) < bj[1]:
best[i + 1] = bi
for m in matches[i]:
j = i + len(m)
bj = best[j]
score = bi[0] + len(m)
if score > bj[0] or score == bj[0] and len(bi[1]) < len(bj[1]):
best[j] = (score, bi[1] + [m])
return best[n][1]
文章来源: find best subset from list of strings to match a given string
