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

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。

- Kawu

---

那么你实际上是在寻找最长公共子序列吗？ - Konrad Rudolph

@KonradRudolph 这是在询问最长公共前缀，而不是子序列。 - Asclepius

@KonradRudolph 这是在询问最长公共前缀，而不是子序列。 - undefined

嘿！我不是一个物体。☝️ - Kawu

嘿！我不是一个物体☝️ - undefined

Answer 1

不要重复造轮子： 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

- Ned Batchelder

---

@sramij 不完全正确！对字符串使用min()和max()是按字典顺序找到最小和最大值。因此，当最小值和最大值具有相同的第一个字母时，它们之间的所有其他单词也必须具有相同的字母，并依此类推。 - Petr

参数需要是有效的路径名吗？如果不是会发生什么？文档上没有提到，所以我不确定它是否可用于任意字符串。 - hochl

@hochl 不是的。这段代码只是查看字符串，而不是路径。如果它们恰好都是路径，请注意这个前缀 commonprefix({"/aaA/b", "/aaB/b"}) == "/aa"，这可能不是您想要使用的路径。 - Jesse Chisholm

如果您确实需要有效路径，请查看姊妹函数os.path.commonpath。从文档中可以看到：“与commonprefix()不同，它返回一个有效的路径。” - AneesAhmed777

告诉面试官们：“永远不要改写任何已提供的内容。”作为一条认真且可能有建设性的评论，考虑不要提供该函数的源代码，因为乍一看我错过了它已经是 os.path.commonprefix 的一部分的声明。 - ijoseph

Answer 2

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

- senderle

---

请在Python3中将itertools.izip(*strings)替换为zip(*strings)。 - Regis May

Answer 3

这是我的解决方案:

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]

- MRAB

Answer 4

以下是一种可行的解决方案，但可能效率不高。

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)

对于小字符串集，上述方法没有任何问题。但对于较大的字符串集，我个人会编写另一种手动解决方案，逐个检查每个字符，并在出现差异时停止。

从算法上讲，这产生了相同的过程，但是可能可以避免构造列表。

- phimuemue

Answer 5

这里有一个简单而干净的解决方案。思路是使用zip()函数将所有字符排列在一起，将它们放入第一个字符列表、第二个字符列表...第n个字符列表中。然后迭代每个列表以检查它们是否仅包含一个值。

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_

- Patmanizer

---

欢迎来到Stack Overflow！虽然这段代码片段可能解决了问题，但是包括解释如何和为什么解决问题会非常有帮助，以提高您的帖子质量。请记住，您正在回答未来读者的问题，而不仅仅是现在提问的人！请[编辑]您的答案以添加解释，并指出适用的限制和假设。 - Toby Speight

这怎么算是干净的？ - thang

怎么会不干净呢？其他的解决方案都用了代码块，而逻辑简单到只需要一个赋值语句就可以了。 - Patmanizer

Answer 6

这段代码的第二行对输入字符串中的每个字符使用reduce函数。它返回一个由N+1个元素组成的列表，其中N是最短输入字符串的长度。

在lot中，每个元素要么是输入字符（如果所有输入字符串在该位置匹配），要么是None。lot.index(None)是lot中第一个None的位置：即公共前缀的长度。out即为该公共前缀。

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

- Mano Bastardo

Answer 7

出于好奇心，我找到了另一种方法来实现这个：

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函数，这是一个非常优雅的函数。

- ThePhysicist

Answer 8

这里提供了一种使用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)])

- skeptichacker

Answer 9

在不使用itertools的情况下，为了没有特定的原因，在一行中迭代每个字符：

''.join([z[0] for z in zip(*(list(s) for s in strings)) if all(x==z[0] for x in z)])

- angus l

Answer 10

从给定的输入字符串中查找所有单词的公共前缀，如果没有公共前缀，则打印-1。

stringList = ['my_prefix_what_ever', 'my_prefix_what_so_ever', 'my_prefix_doesnt_matter']
len2 = len( stringList )
if len2 != 0:
    # let shortest word is prefix
    prefix = min( stringList )
    for i in range( len2 ):
        word = stringList[ i ]
        len1 = len( prefix )
        # slicing each word as lenght of prefix
        word = word[ 0:len1 ]
        for j in range( len1 ):
            # comparing each letter of word and prefix
            if word[ j ] != prefix[ j ]:
                # if letter does not match slice the prefix
                prefix = prefix[ :j ]
                break # after getting comman prefix move to next word
    if len( prefix ) != 0:
        print("common prefix: ",prefix)
    else:
        print("-1")
else:
     print("string List is empty") 

- jugesh