Python:确定一组(类似)string的前缀

我有一组string,例如

my_prefix_what_ever my_prefix_what_so_ever my_prefix_doesnt_matter 

我只想find这些string中最长的公共部分,这里是前缀。 在上面的结果应该是

 my_prefix_ 

string

 my_prefix_what_ever my_prefix_what_so_ever my_doesnt_matter 

应该导致前缀

 my_ 

在Python中有没有一种相对无痛的方式来确定前缀(而不必手动迭代每个字符)?

PS:我正在使用Python 2.6.3。

    永远不要重写什么提供给你: os.path.commonprefix正是这样做:

    返回列表中所有path前缀的最长path前缀(逐个字符)。 如果列表为空,则返回空string( '' )。 请注意,这可能会返回无效path,因为它一次处理一个字符。

    与其他答案进行比较,代码如下:

     # Return the longest prefix of all list elements. def commonprefix(m): "Given a list of pathnames, returns the longest common leading component" if not m: return '' s1 = min(m) s2 = max(m) for i, c in enumerate(s1): if c != s2[i]: return s1[:i] return s1 

    Ned Batchelder可能是对的。 但为了它的乐趣,这里是使用itertools更有效的phimuemue的答案版本。

     import itertools strings = ['my_prefix_what_ever', 'my_prefix_what_so_ever', 'my_prefix_doesnt_matter'] def all_same(x): return all(x[0] == y for y in x) char_tuples = itertools.izip(*strings) prefix_tuples = itertools.takewhile(all_same, char_tuples) ''.join(x[0] for x in prefix_tuples) 

    作为可读性的冒犯,这是一个单行版本:)

     >>> from itertools import takewhile, izip >>> ''.join(c[0] for c in takewhile(lambda x: all(x[0] == y for y in x), izip(*strings))) 'my_prefix_' 

    这是我的解决scheme:

     a = ["my_prefix_what_ever", "my_prefix_what_so_ever", "my_prefix_doesnt_matter"] prefix_len = len(a[0]) for x in a[1 : ]: prefix_len = min(prefix_len, len(x)) while not x.startswith(a[0][ : prefix_len]): prefix_len -= 1 prefix = a[0][ : prefix_len] 

    以下是一个工作,但可能相当低效的解决scheme。

     a = ["my_prefix_what_ever", "my_prefix_what_so_ever", "my_prefix_doesnt_matter"] b = zip(*a) c = [x[0] for x in b if x==(x[0],)*len(x)] result = "".join(c) 

    对于一小串琴弦来说,上述没有任何问题。 但是对于更大的集合,我个人会编写另一个手动解决scheme,逐个检查每个字符,并在有差异时停止。

    在algorithm上,这产生相同的过程,但是,可以避免构build列表c

    出于好奇,我想出了另一种方法来做到这一点:

     def common_prefix(strings): if len(strings) == 1:#rule out trivial case return strings[0] prefix = strings[0] for string in strings[1:]: while string[:len(prefix)] != prefix and prefix: prefix = prefix[:len(prefix)-1] if not prefix: break return prefix strings = ["my_prefix_what_ever","my_prefix_what_so_ever","my_prefix_doesnt_matter"] print common_prefix(strings) #Prints "my_prefix_" 

    正如Ned指出,使用os.path.commonprefix可能更好,这是一个相当优雅的function。

    第二行对inputstring中的每个字符都使用了reduce函数。 它返回N + 1个元素的列表,其中N是最短inputstring的长度。

    批次中的每个元素都是(a)input字符,如果所有inputstring在该位置匹配,或者(b)无。 lot.index(None)是批中第一​​个None的位置:通用前缀的长度。 那是常用的前缀。

     val = ["axc", "abc", "abc"] lot = [reduce(lambda a, b: a if a == b else None, x) for x in zip(*val)] + [None] out = val[0][:lot.index(None)] 

    这是使用OrderedDict最小代码的另一种方法。

     import collections import itertools def commonprefix(instrings): """ Common prefix of a list of input strings using OrderedDict """ d = collections.OrderedDict() for instring in instrings: for idx,char in enumerate(instring): # Make sure index is added into key d[(char, idx)] = d.get((char,idx), 0) + 1 # Return prefix of keys while value == length(instrings) return ''.join([k[0] for k in itertools.takewhile(lambda x: d[x] == len(instrings), d)]) 

    这是一个简单的清洁解决scheme。 这个想法是使用zip()函数将所有字符排列在第一个字符的列表中,第二个字符的列表中,…第n个字符的列表中。 然后迭代每个列表来检查它们是否只包含1个值。

     a = ["my_prefix_what_ever", "my_prefix_what_so_ever", "my_prefix_doesnt_matter"] list = [all(x[i] == x[i+1] for i in range(len(x)-1)) for x in zip(*a)] print a[0][:list.index(0) if list.count(0) > 0 else len(list)] 

    输出:my_prefix_