# Check whether set of strings is prefix-free via lexicographic sort?

I have a set of strings and would like to establish whether the set has the prefix property, which basically means that no string in the set is a prefix of any other string in the set. So {a, b} is prefix-free (has the prefix property) while {a, b, ba} is not prefix-free (lacks the prefix property) because the entire string b is a prefix of ba.

One can of course implement this with a double-loop for quadratic performance. In JavaScript (so you can pop open your browser’s JS Console and try it, if so inclined):

function isPrefixCode(strings) {
for (const i of strings) {
for (const j of strings) {
if (j === i) {
continue;
}
if (i.startsWith(j)) {
return false;
}
}
}
return true;
}
isPrefixCode(new Set('a b c'.split(' '))) // true
isPrefixCode(new Set('ba b c'.split(' '))) // false


I think one can do better by sorting the set of strings lexicographically ($N \log N$), then comparing each element to its previous one (linear). So:

function isPrefixCodeLinear(strings) {
strings = Array.from(strings).sort();
for (const [i, s] of strings.entries()) {
if (i === 0) {
continue;
}
const prev = strings[i - 1];
if (s.startsWith(prev)) {
return false;
};
}
return true;
}
isPrefixCodeLinear(new Set('a b c'.split(' '))) // true
isPrefixCodeLinear(new Set('ba b c'.split(' '))) // false


This linearithmic algorithm seems to work for the tests I’ve come up with (and ~100x speedup over the quadratic double-loop algorithm on a 1000-string example), but I’d like to ask

1. if this approach based on lexicographic sorting is guaranteed to work,
2. if this approach has a name, and
3. if the prefix property has a more common term in computer science, or
4. if there are other algorithms that can solve it.

(I found this question on StackOverflow, about finding whether any entry in a set of strings is prefixed by a specific given string, How to search whether a string is a prefix of strings stored in a set?, which is a related problem to mine, but here I want to consider not just any one string but all the strings in the set.)

• This algorithm is correct, but depending on what $N$ is intended to represent, the running time is not $O(N \lg N)$. Consider a set of $N$ strings, where each string starts with $N$ a's. Then the running time is more like $O(N^2 \lg N)$, because comparing a pair of strings takes $O(N)$ time rather than $O(1)$ time. – D.W. Sep 9 '16 at 18:46
• It will be $O(N \log N + N)$ in that case, if you obtain the LCP's during the sort. – KWillets Sep 9 '16 at 19:53
• Oops, my brain is elsewhere today. N^2 in the second term. – KWillets Sep 9 '16 at 20:28