Longest Common Prefix in an array of Strings

Please be brutal, and treat this as if I was at an interview at a top 5 tech firm.


Question: Write a function to find the longest common prefix string
amongst an array of strings.

Time it took: 17 minutes

Worst case complexity analysis: n possible array elements, each can have length m that we are traversing, hence O(nm); m could be a constant, since it's rare to find a string with length, so in a sense, I imagine this could be treated as O(n constant length(m)) = O(n)?

Space complexity analysis: O(n)

public String longestCommonPrefix(String[] strs) {
    String longestPrefix = "";
    if(strs.length>0){
        longestPrefix = strs[0];
    }
    for(int i=1; i<strs.length; i++){
        String analyzing = strs[i];
        int j=0;
        for(; j<Math.min(longestPrefix.length(), strs[i].length()); j++){
            if(longestPrefix.charAt(j) != analyzing.charAt(j)){
                break;
            }
        }
        longestPrefix = strs[i].substring(0, j);
    }
    return longestPrefix;
}

Pure functions should generally be declared static.

You shouldn't need to take substrings in a loop — that's inefficient. Think of scanning a two-dimensional ragged array of characters. Check that all of the first characters match, then that all of the second characters match, and so on until you find a mismatch, or one of the strings is too short.

public static String longestCommonPrefix(String[] strings) {
    if (strings.length == 0) {
        return "";   // Or maybe return null?
    }

    for (int prefixLen = 0; prefixLen = strings[i].length() ||
                 strings[i].charAt(prefixLen) != c ) {
                // Mismatch found
                return strings[i].substring(0, prefixLen);
            }
        }
    }
    return strings[0];
}

Space complexity: O(1).

Worst-case time complexity: O(n m) to scan every character in every string.

StackExchange Code Review Q#46965, answer score: 13