Skip to content

Instantly share code, notes, and snippets.

@stanio
Created December 16, 2019 22:32
Show Gist options
  • Save stanio/ec307135696ded1f6b2ef7dbe576107d to your computer and use it in GitHub Desktop.
Save stanio/ec307135696ded1f6b2ef7dbe576107d to your computer and use it in GitHub Desktop.
Longest Common Prefix using Binary Search
//package ;
/**
* @see <a href="https://www.geeksforgeeks.org/longest-common-prefix-using-binary-search/">Longest
* Common Prefix using Binary Search</a>
*/
public class StringUtil {
public static String commonPrefix(CharSequence... strings) {
int low = 0, high = minLength(strings) - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (startWith(strings, low, mid)) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return (low == 0) ? "" : strings[0].subSequence(0, low).toString();
}
private static boolean startWith(CharSequence[] strings, int start, int end) {
CharSequence prefix = strings[0];
for (int i = 1, n = strings.length; i < n; i++) {
CharSequence str = strings[i];
for (int j = start; j <= end; j++) {
if (str.charAt(j) != prefix.charAt(j)) {
return false;
}
}
}
return true;
}
private static int minLength(CharSequence[] strings) {
int min = Integer.MAX_VALUE;
for (int i = 0, n = strings.length; i < n; i++) {
int len = strings[i].length();
if (len < min) {
min = len;
}
}
return min;
}
public static void main(String[] args) {
System.out.println(commonPrefix("geeksforgeeks", "geeks", "geek", "geezer"));
System.out.println(commonPrefix("apple", "ape", "april"));
System.out.println(commonPrefix("abcd"));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment