LeetCode. 14. Longest Common Prefix

[Link] https://leetcode.com/problems/longest-common-prefix/

Approach

Scan the first string from left to right. At each position, compare its character with the character at the same position in every other string. The first mismatch ends the shared prefix, so return the part of the first string before that position.

Before comparing a position, check whether each other string is long enough to contain it. If it is shorter, the common prefix ends at its length. The scan never indexes past a string’s end, and the first string itself is the candidate prefix, so no separate prefix buffer is needed.

The algorithm inspects at most the characters covered by the shortest string across the input, for O(S) total inspected characters, where S is the sum of the lengths of all strings. It uses O(1) auxiliary space, excluding the returned substring.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }

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