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
- if this approach based on lexicographic sorting is guaranteed to work,
- if this approach has a name, and
- if the prefix property has a more common term in computer science, or
- 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.)