Skip to content

Instantly share code, notes, and snippets.

@jeffque
Last active February 15, 2023 01:45
Show Gist options
  • Save jeffque/d6433a4dcab0016fd00d474a340e20d4 to your computer and use it in GitHub Desktop.
Save jeffque/d6433a4dcab0016fd00d474a340e20d4 to your computer and use it in GitHub Desktop.
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class LongestCommonPrefix {
static final Holder FIRST_HOLDER = new Holder("", 0) {
@Override
Holder acc(String another) {
return another.isEmpty()? EMPTY_HOLDER: new Holder(another);
}
@Override
Holder acc(Holder another) {
return another;
}
};
static final Holder EMPTY_HOLDER = new Holder("", 0) {
@Override
Holder acc(String another) {
return this;
}
@Override
Holder acc(Holder another) {
return this;
}
};
static class Holder {
final String prefix;
final int len;
Holder(String prefix) {
this(prefix, prefix.length());
}
Holder(String prefix, int len) {
this.prefix = prefix;
this.len = len;
}
Holder acc(String another) {
return acc(another, another.length());
}
Holder acc(Holder another) {
if (another == FIRST_HOLDER) {
return this;
}
return acc(another.prefix, another.len);
}
private Holder acc(String another, int anotherLen) {
int x = anotherLen <= len? anotherLen: len;
for (int i = 0; i < x; i++) {
if (prefix.charAt(i) != another.charAt(i)) {
if (i == 0) {
return EMPTY_HOLDER;
}
return new Holder(another, i);
}
}
return new Holder(another, x);
}
String prefix() {
return prefix.substring(0, len);
}
}
private static String prefix(String[] args) {
return Stream.of(args)
.parallel()
.reduce(FIRST_HOLDER, Holder::acc, Holder::acc)
.prefix();
}
public static void main(String... args) {
System.out.println(prefix(args));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment