4
\$\begingroup\$

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

        return recursiveChecker(strIndex + 1, list);
    }
}
\$\endgroup\$
2

1 Answer 1

4
\$\begingroup\$
  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[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;
    }
    
  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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.