Find the longest common starting substring in a set of strings

A ruby version based on @Svante's algorithm. Runs ~3x as fast as my first one.

def common_prefix set
i=0
rest=set[1..-1]
set[0].each_byte{|c|
rest.each{|e|return set[0][0...i] if e[i]!=c}
i+=1
}
set
end

In Python I wouldn't use anything but [the existing `commonprefix` function I showed in another answer](#1916632), but I couldn't help to reinvent the wheel `:P`. This is my iterator-based approach:

>>> a = 'interspecies interstelar interstate'.split()
>>>
>>> from itertools import takewhile, chain, izip as zip, imap as map
>>> ''.join(chain(*takewhile(lambda s: len(s) == 1, map(set, zip(*a)))))
'inters'

**Edit:** Explanation of how this works.

`zip` generates tuples of elements taking one of each item of `a` at a time:

In [6]: list(zip(*a)) # here I use list() to expand the iterator
Out[6]:
[('i', 'i', 'i'),
('n', 'n', 'n'),
('t', 't', 't'),
('e', 'e', 'e'),
('r', 'r', 'r'),
('s', 's', 's'),
('p', 't', 't'),
('e', 'e', 'a'),
('c', 'l', 't'),
('i', 'a', 'e')]

By mapping `set` over these items, I get a series of unique letters:

In [7]: list(map(set, _)) # _ means the result of the last statement above
Out[7]:
[set(['i']),
set(['n']),
set(['t']),
set(['e']),
set(['r']),
set(['s']),
set(['p', 't']),
set(['a', 'e']),
set(['c', 'l', 't']),
set(['a', 'e', 'i'])]

`takewhile(predicate, items)` takes elements from this while the predicate is True; in this particular case, when the `set`s have one element, i.e. all the words have the same letter at that position:

In [8]: list(takewhile(lambda s: len(s) == 1, _))
Out[8]:
[set(['i']),
set(['n']),
set(['t']),
set(['e']),
set(['r']),
set(['s'])]

At this point we have an iterable of sets, each containing one letter of the prefix we were looking for. To construct the string, we `chain` them into a single iterable, from which we get the letters to `join` into the final string.

The magic of using iterators is that all items are generated on demand, so when `takewhile` stops asking for items, the zipping stops at that point and no unnecessary work is done. Each function call in my one-liner has a implicit `for` and an implicit `break`.

It's not code golf, but you asked for somewhat elegant, and I tend to think recursion is fun. Java.

/** Recursively find the common prefix. */
public String findCommonPrefix(String[] strings) {

int minLength = findMinLength(strings);

if (isFirstCharacterSame(strings)) {
return strings[0].charAt(0) + findCommonPrefix(removeFirstCharacter(strings));
} else {
return "";
}
}

/** Get the minimum length of a string in strings[]. */
private int findMinLength(final String[] strings) {
int length = strings[0].size();
for (String string : strings) {
if (string.size() < length) {
length = string.size();
}
}
return length;
}

/** Compare the first character of all strings. */
private boolean isFirstCharacterSame(String[] strings) {
char c = string[0].charAt(0);
for (String string : strings) {
if (c != string.charAt(0)) return false;
}

return true;
}

/** Remove the first character of each string in the array,
and return a new array with the results. */
private String[] removeFirstCharacter(String[] source) {
String[] result = new String[source.length];
for (int i=0; i<result.length; i++) {
result[i] = source[i].substring(1);
}
return result;
}

This is by no means elegant, but if you want concise:

Ruby, 71 chars
--------------

def f(a)b=a[0];b[0,(0..b.size).find{|n|a.any?{|i|i[0,n]!=b[0,n]}}-1]end

If you want that unrolled it looks like this:

def f(words)
first_word = words[0];
first_word[0, (0..(first_word.size)).find { |num_chars|
words.any? { |word| word[0, num_chars] != first_word[0, num_chars] }
} - 1]
end

Javascript clone of [AShelly](

[To see links please register here]

)'s excellent answer.

Requires `Array#reduce` which is supported only in firefox.

var strings = ["interspecies", "intermediate", "interrogation"]
var sub = strings.reduce(function(l,r) {
while(l!=r.slice(0,l.length)) {
l = l.slice(0, -1);
}
return l;
});

I would do the following:

1. Take the first string of the array as the initial *starting substring*.
2. Take the next string of the array and compare the characters until the end of one of the strings is reached or a mismatch is found. If a mismatch is found, reduce *starting substring* to the length where the mismatch was found.
3. Repeat step 2 until all strings have been tested.

Here’s a JavaScript implementation:

var array = ["interspecies", "interstelar", "interstate"],
prefix = array[0],
len = prefix.length;
for (i=1; i<array.length; i++) {
for (j=0, len=Math.min(len,array[j].length); j<len; j++) {
if (prefix[j] != array[i][j]) {
len = j;
prefix = prefix.substr(0, len);
break;
}
}
}

Doesn't seem that complicated if you're not too concerned about ultimate performance:

def common_substring(data)
data.inject { |m, s| s[0,(0..m.length).find { |i| m[i] != s[i] }.to_i] }
end

One of the useful features of inject is the ability to pre-seed with the first element of the array being interated over. This avoids the nil memo check.

puts common_substring(%w[ interspecies interstelar interstate ]).inspect
# => "inters"
puts common_substring(%w[ feet feel feeble ]).inspect
# => "fee"
puts common_substring(%w[ fine firkin fail ]).inspect
# => "f"
puts common_substring(%w[ alpha bravo charlie ]).inspect
# => ""
puts common_substring(%w[ fork ]).inspect
# => "fork"
puts common_substring(%w[ fork forks ]).inspect
# => "fork"

*Update:* If golf is the game here, then 67 characters:

def f(d)d.inject{|m,s|s[0,(0..m.size).find{|i|m[i]!=s[i]}.to_i]}end

In Python:

>>> from os.path import commonprefix
>>> commonprefix('interspecies interstelar interstate'.split())
'inters'

Here's a solution using regular expressions in Ruby:

def build_regex(string)
arr = []
arr << string.dup while string.chop!
Regexp.new("^(#{arr.join("|")})")
end

def substring(first, *strings)
strings.inject(first) do |accum, string|
build_regex(accum).match(string)[0]
end
end

Python 2.6 (r26:66714, Oct 4 2008, 02:48:43)

>>> a = ['interspecies', 'interstelar', 'interstate']

>>> print a[0][:max(
[i for i in range(min(map(len, a)))
if len(set(map(lambda e: e[i], a))) == 1]
) + 1]

inters

* ``i for i in range(min(map(len, a)))``, number of maximum lookups can't be greater than the length of the shortest string; in this example this would evaluate to ``[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]``

* ``len(set(map(lambda e: e[i], a)))``, 1) create an array of the ``i-th``character for each string in the list; 2) make a set out of it; 3) determine the size of the set

* ``[i for i in range(min(map(len, a))) if len(set(map(lambda e: e[i], a))) == 1]``, include just the characters, for which the size of the set is 1 (all characters at that position were the same ..); here it would evaluate to ``[0, 1, 2, 3, 4, 5]``

* finally take the ``max``, add one, and get the substring ...

Note: the above does not work for ``a = ['intersyate', 'intersxate', 'interstate', 'intersrate']``, but this would:

>>> index = len(
filter(lambda l: l[0] == l[1],
[ x for x in enumerate(
[i for i in range(min(map(len, a)))
if len(set(map(lambda e: e[i], a))) == 1]
)]))
>>> a[0][:index]
inters