Longest Common Prefix

NeetCode: Longest Common Prefix · LeetCode: 14. Longest Common Prefix · Difficulty: Easy

Write a function to find the longest common prefix string among an array of strings. If there is no common prefix, return an empty string.

Example

Text

Input:  strs = ["flower", "flow", "flight"]    Output: "fl"
Input:  strs = ["dog", "racecar", "car"]       Output: ""

Brute force: test every prefix length

Try each prefix length len from the shortest string's length down to 0, and check whether every string starts with the first string's prefix of that length. Every check re-compares the same characters, so the work grows quadratically with the string length. substring(0, len) copies the prefix, and startsWith compares it character by character.

Java

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        int minLen = Integer.MAX_VALUE;
        for (String s : strs) {
            minLen = Math.min(minLen, s.length());
        }
        for (int len = minLen; len >= 0; len--) {
            String prefix = strs[0].substring(0, len);
            boolean all = true;
            for (String s : strs) {
                if (!s.startsWith(prefix)) {
                    all = false;
                    break;
                }
            }
            if (all) {
                return prefix;
            }
        }
        return "";
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println("\"" + s.longestCommonPrefix(new String[]{"flower", "flow", "flight"}) + "\"");
        System.out.println("\"" + s.longestCommonPrefix(new String[]{"dog", "racecar", "car"}) + "\"");
        System.out.println("\"" + s.longestCommonPrefix(new String[]{}) + "\"");
    }
}

Output

"fl"
""
""

Time: O(n · m^2) for n strings with shortest length m. Space: O(m).

Optimal: vertical scan

Compare column by column: take character i of the first string and check that every other string has the same character at i. The first mismatch (or a string that is too short) ends the scan, and the answer is everything before that column. Each character is compared at most once.

Java

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

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println("\"" + s.longestCommonPrefix(new String[]{"flower", "flow", "flight"}) + "\"");
        System.out.println("\"" + s.longestCommonPrefix(new String[]{"dog", "racecar", "car"}) + "\"");
        System.out.println("\"" + s.longestCommonPrefix(new String[]{}) + "\"");
    }
}

Output

"fl"
""
""

Time: O(S) where S is the total number of characters (at most n · m comparisons). Space: O(m) for the returned string.

charAt(i) returns a 16-bit char, and substring(0, i) cuts at a char index. For this problem's lowercase English letters that is exact. For text with characters outside the basic range, a cut can fall between the two halves of a surrogate pair, so such input needs code-point handling. An empty array returns "", and a single string returns itself.