# Finding the common prefix in a list of strings

Given a list of strings, my task is to find the common prefix.

Sample input: ["madam", "mad", "mast"] Sample output: "ma"

Sample input: ["question", "method"] Sample output: ""

Below is my solution, I'd be happy for help improving the algorithm (I'm open to totally different approaches) or general code improvement tips. Thanks :)

public class PreFixer {

public static void main(String[] args) {
if(args.length < 1) {
System.out.println("invalid arguments");
return;
}
String commongPrefix = getCommonPrefix(args);
System.out.println("Common Prefix for list is : " + commongPrefix);
}

private static String getCommonPrefix (String[] list){
int matchIndex = recursiveChecker(0, list);
return list.substring(0, matchIndex);
}

private static int recursiveChecker(int strIndex, String[] list){

for(int x=0; x<list.length; x++) {
if(strIndex >= list[x].length()){
return strIndex;
}

if(list.charAt(strIndex) != list[x].charAt(strIndex)) {
return strIndex;
}
}

return recursiveChecker(strIndex + 1, list);
}
}

• See codereview.stackexchange.com/a/65114/35991 for a possible different approach. Mar 19, 2015 at 21:54
• This approach is tail recursive, so that does improve performance.. Mar 20, 2015 at 7:51

1. There are some inconsistencies in your code style: sometimes you do put a space before an opening curly bracket, sometimes you don't. It is a good practice to adhere to one style(in this case, it is conventional to have a whitespace there). It is also conventional to surround all binary operators with whitespaces to make the code more readable. For instance, for(int x = 0; x < list.length; x++) looks better than
for(int x=0; x<list.length; x++).

2. In terms of time complexity, you algorithm is optimal(it is linear in the size of input). However, if it is supposed to work with long strings, I'd use iteration instead of recursion(it gets a StackOverflowError when the strings get really big). Here is my iterative solution:

public static String getLongestCommonPrefix(String[] strings) {
int commonPrefixLength = 0;
while (allCharactersAreSame(strings, commonPrefixLength)) {
commonPrefixLength++;
}
return strings.substring(0, commonPrefixLength);
}

private static boolean allCharactersAreSame(String[] strings, int pos) {
String first = strings;
for (String curString : strings) {
if (curString.length() <= pos
|| curString.charAt(pos) != first.charAt(pos)) {
return false;
}
}
return true;
}

3. In general, each class should have single responsibility(that it, you might create two separate classes here: one for computing the longest prefix and the other one for checking and parsing command-line arguments). But I think it is fine to have one class here(the entire class is pretty small) as long as the format of arguments is not going to change in the future.