HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Finding the common prefix in a list of strings

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
thefindingprefixliststringscommon

Problem

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 = list[x].length()){
                return strIndex;
            }

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

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

Solution

-
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

-
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[0].substring(0, commonPrefixLength);
}

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


-
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.

Code Snippets

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

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

Context

StackExchange Code Review Q#84523, answer score: 4

Revisions (0)

No revisions yet.