确定多个字符串的公共前缀

Question

我有一组字符串，比如：

my_prefix_what_ever
my_prefix_what_so_ever
my_prefix_doesnt_matter

我想找到这些字符串中最长的公共部分，也就是它们的前缀。在上面的例子中，结果应该是：

my_prefix_

这些字符串

my_prefix_what_ever
my_prefix_what_so_ever
my_doesnt_matter

应该得到的前缀是：

my_

有没有一种比较简单的方法可以在Python中找到这个前缀（不需要手动逐个字符去检查）？

附：我使用的是Python 2.6.3。

Answer 1

这是我的解决方案：

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]

Answer 2

Ned Batchelder 可能是对的。不过为了好玩，这里有一个更高效的版本，使用了phimuemue 的答案中的 itertools。

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

Answer 3

不要重新编写已经提供给你的内容：os.path.commonprefix 就是这样做的：

这个功能会返回一个最长的路径前缀（逐个字符比较），这个前缀是列表中所有路径的共同开头。如果列表是空的，它会返回一个空字符串（''）。需要注意的是，由于它是逐个字符处理的，所以可能会返回一些无效的路径。

为了和其他回答做个对比，这里是代码：

# 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