Longest Common Prefix

Given an array of lowercase strings, return the longest string that is a prefix of all of them. If there is none, return an empty string.

LeetCode: 14. Longest Common Prefix

Example

Input:  ["apple", "ape", "april"]        Output: "ap"
Input:  ["flower", "flow", "flight"]     Output: "fl"
Input:  ["dog", "racecar", "car"]        Output: ""

Some versions of this problem return "-1" when there is no common prefix. Returning an empty String is the natural Java equivalent, and a caller can map it to anything.

Brute force: horizontal scanning

Start with the first string as the candidate prefix. For each other string, shorten the candidate until the string starts with it.

public class Main {
    static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);
            }
        }
        return prefix;
    }

    public static void main(String[] args) {
        System.out.println("\"" + longestCommonPrefix(new String[]{"apple", "ape", "april"}) + "\"");
        System.out.println("\"" + longestCommonPrefix(new String[]{"flower", "flow", "flight"}) + "\"");
        System.out.println("\"" + longestCommonPrefix(new String[]{"dog", "racecar", "car"}) + "\"");
    }
}

"ap"
"fl"
""

Time: O(n·L + L²), where n is the number of strings and L is the length of the first one: every string needs one successful startsWith check, and the prefix shrinks at most L times in total, each failed check costing up to O(L). Each substring copies up to L characters, which stays within the same bound. Space: O(L) for the candidate copies.

The loop always ends, because the empty string is a prefix of every string.

Optimal: vertical scanning

Compare column by column: character i of the first string against character i of every other string. Stop at the first column where a string is too short or differs. Only the columns of the common prefix, plus the one where it ends, are read.

public class Main {
    static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String first = strs[0];
        for (int i = 0; i < first.length(); i++) {
            char c = first.charAt(i);
            for (int k = 1; k < strs.length; k++) {
                if (i >= strs[k].length() || strs[k].charAt(i) != c) {
                    return first.substring(0, i);
                }
            }
        }
        return first;
    }

    public static void main(String[] args) {
        System.out.println("\"" + longestCommonPrefix(new String[]{"apple", "ape", "april"}) + "\"");
        System.out.println("\"" + longestCommonPrefix(new String[]{"flower", "flow", "flight"}) + "\"");
        System.out.println("\"" + longestCommonPrefix(new String[]{"dog", "racecar", "car"}) + "\"");
        System.out.println("\"" + longestCommonPrefix(new String[]{"alone"}) + "\"");
        System.out.println("\"" + longestCommonPrefix(new String[]{"abc", ""}) + "\"");
    }
}

"ap"
"fl"
""
"alone"
""

Time: O(n·p), where p is the length of the common prefix. That is never more than the total number of characters. Space: O(p) for the returned substring.

charAt returns a 16-bit char (a UTF-16 code unit). The comparison is correct for lowercase ASCII. A character outside the Basic Multilingual Plane uses two code units, so a prefix cut between them could split it. For arbitrary text, compare code points with codePointAt.

Edge cases

• Empty array: "".
• One string: the string itself.
• An empty string in the array: "".
• Identical strings: the whole string.

A trie also solves this: insert every string, then walk down from the root while the node has exactly one child and is not the end of a word. It pays off only when the same set of strings is queried repeatedly.