Array and String

Solution and explanation

Problem

Find the longest prefix shared by all strings in an array.

["flower", "flow", "flight"] → "fl"
["dog", "racecar", "car"]    → ""

Approach 1: vertical scanning (optimal and simple)

Compare characters column by column; stop at the first mismatch or the end of any string.

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

Approach 2: sort and compare first and last

After sorting, the common prefix of the whole array equals the common prefix of the first and last strings.

static String lcpSorted(String[] strs) {
    Arrays.sort(strs);
    String a = strs[0], b = strs[strs.length - 1];
    int i = 0;
    while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) i++;
    return a.substring(0, i);
}

Complexity

• Vertical scanning: O(S) where S is the total number of characters, O(1) extra space.
• Sorting: O(n · m log n) for n strings of length m.
• A trie also works (useful when many queries share the same word list).