Find common substring that starts a set of strings

How would you in a pythonic manner write a function that returns the common substring found at the beginning of a set of strings? This is my ugly attempt:

def common_start(s):
l = len(s)
if l == 0: return None
elif l == 1: return next(iter(s))
else:
i = iter(s)
start = next(i)
while start != "":
if all(ii.startswith(start) for ii in i):
return start
else:
i = iter(s)
start = start[:-1]
next(i) # were comparing againt the first item, so we don't need it
else:
return ""

s = set(("abc1","abcd","abc","abc abc"))
common_start(s) # "abc"

s = set(("ab","abcd","abc","abc abc"))
common_start(s) # "ab"

s = set(("ab",))
common_start(s) # "ab"

s = set(("","abcd","abc","abc abc"))
common_start(s) # ""

s = set()
common_start(s) # None

• Is there a reason why you want common_start({}) == None instead of ""? Feb 19, 2020 at 7:56

Your usage of iter() and next() is unnecessarily confusing. This comes from the requirement of using a set as an input, where sets are not indexable.

If you passed in a list, then instead of this:

   elif l == 1: return next(iter(s))


you could write:

   elif l == 1: return s[0]


which is much clearer. It gets even clearer when you remove the iterator from the all( ... for ii in i), which necessitates using i = iter(s); next(i) to reset the iterator. Here is the updated code:

def common_start(*s):
l = len(s)
if l == 0:
return None
elif l == 1:
return s[0]

start = s[0]
while start != "" and not all(ii.startswith(start) for ii in s[1:]):
start = start[:-1]

return start


Usage:

>>> s = { "abc1", "abcd", "abc", "abc abc" }
>>> common_start(*s)
'abc'


The *s explodes the set into a list of arguments.

Reduce

What is the common prefix among N strings? It would be the same as taking the common prefix of the first two strings, and using that compute the common prefix with the third string, and so on, until you reach the last string.

common_start({a, b, c, d}) == common_prefix(common_prefix(common_prefix(a, b), c), d)


Which leads us to functools.reduce().

from functools import reduce

def common_start(s):
if s:
return reduce(common_prefix, s)

return None


Now, we just need a function to return the common prefix of two strings.

As an example, this works, although is a bit cryptic. You might be able to come up with a simpler, possibly faster method:

from itertools import takewhile

def common_prefix(a, b):
return a[:len(list(takewhile((lambda z: z[0] == z[1]), zip(a, b))))]


os.path

Surprisingly, Python comes with the required function built-in to the os.path module. Just need to convert the set to a list, and handle the empty set to None special case:

import os

def common_start(s):
if s:
return os.path.commonprefix(list(s))

return None

• Nice answer. Smart use of reduce. But I'd personally not pass common_prefix as a PR. Feb 15, 2020 at 22:00
• @Peilonrayz PR? Feb 15, 2020 at 22:11
• Pull request :) Feb 15, 2020 at 22:12
• Also that os.path solution is amazing. Feb 15, 2020 at 22:13
• @Peilonrayz Ah yes. It was one part showing off with a one-line solution, and one part ensuring it didn't get used as someone's homework solution. I haven't done any performance testing on it; it may be fast, it may be slow. It would require a hell of a justification for me to accept it as a PR too. ;) Feb 15, 2020 at 22:18

You should read PEP 8 and get a linter; pycodestyle, pylint, flake8, prospector, coala. It doesn't matter which one, just get one and use it.

• Indenting with 3 spaces is awful, no-one can easily interact with your code.
I've never in my life seen 3 spaces for indentation, it makes me think your post is a joke.
• Variables like s, l and ii are useless.
• It's really bad to put statements on the same line as other statements.

if l == 0: return None


The amount of times I've just not seen the return None with lines like this isn't funny. It's nearly 100%.

• Change your if, elif, else to guard statements and you can dedent your code.
• There's no need for while else, you've not broken from the loop.
• Returning None is just odd at best, change it to an empty string.
• Taking a set as input is really strange, it causes you to have to do next(iter(s)). And you're not even exploiting the benefits of it.
• Using iterators is clever, but not smart. You can just make a new list to contain all but the first value.

Additionally it doesn't really matter if you check against the first value because it's always going to be a subset of itself. Just seems like adding complexity for the sake of complexity.

• You can remove the if l == 1 check.

def common_start(values):
if len(values) != 0:
start = values[0]
while start:
if all(value.startswith(start) for value in values):
return start
start = start[:-1]
return ""


However this isn't the best. If there are $$\s\$$ values, and each have a length $$\l\$$ then your code runs in $$\O(sl^2)\$$ time.

Instead I'd suggest checking the first value against everything once - running in $$\s\$$ time. Since you do this $$\l\$$ times it runs in $$\O(sl)\$$ time.

To do so you can use zip to iterate through all the first characters, then second characters at the same time. From this you can check if they are the same and append them to a temporary list. Finally you return the contents of the list converted to one single string. In the end you would end up with something like salparadise created.

Again I would still make an empty list or set as input return an empty string.

def common(values):
start = []
for characters in zip(*values):
if len(set(characters)) != 1:
break
start.append(characters[0])
return ''.join(start)

• good stuff. +1, I think you raise the bar on how to craft an answer. I will keep mine deleted :) Feb 15, 2020 at 21:32
• @salparadise Oh no, I feel like a bully!!! 😥‎ Feb 15, 2020 at 21:34
• @AJNeufeld FWIW bar was not a typo, I was using it's preposition meaning. I'll leave it so it's easier to understand tho :) Feb 15, 2020 at 21:52
• @Peilonrayz My bad. I read it and found it jarring -- figured it was a typo, but I can see how it actually makes sense with "bar". Feb 15, 2020 at 21:56
• @Baz the quoted if would be a guard statement if the elif after it were an if and the else didn't exist. In short if you return in the body of an if just don't use else or elif. Feb 19, 2020 at 21:06

I would personally prefer that (1) you yield elements one by one, and (2) that you use the built-in functions as much as possible. Python comes with the zip function that allows you to iterate over elements with the same index. That is, zip(* ['ab', 'xyz']) will yield ('a', 'x') and then ('b', 'y'). Notice that it only yields elements up to the shortest string has been exhausted, hence the bounds are dealt with automatically. Notice also that since zip(* ['ab', 'abc', 'abx']) yields ('a', 'a', 'a') and ('b', 'b', 'b'), you can use len(set(elt)) == 1 to verify that the characters are all the same.

Depending on how you want to use the function, I would perhaps yield elements, and perhaps make a wrapper function to turn the result into a string.

def _common_prefix(seq):
"""A generator that yields common elements of a sequence of sequences."""
for e in zip(*seq):
if len(set(e)) != 1:
break
yield e[0]

def common_prefix(seq):
"""Compute the common prefix of a sequence of sequence"""
return "".join(_common_prefix(seq))