Find common substring that starts a set of strings

Question

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

Answer 1

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

Answer 2

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)

Answer 3

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