easyString Basics

Longest Common Prefix

Find the longest prefix shared by every supplied word.

LeetCode ↗

Work through the cases

3 examples

Input notation

One line of space-separated lowercase words.

Expected result

The common prefix, or none if it is empty.

Case 1

Input

flower flow flight

Expected output

fl

Case 2

Input

dog cat

Expected output

none

Case 3

Input

same same

Expected output

same

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is to take the first string as the prefix and shrink it against each later string. n,m ≤ 200, so even a triple loop would pass. A trie works too, but it is heavier than this problem needs. The prefix only ever shrinks: once a column disagrees, a longer prefix cannot exist. Align the strings vertically; position i can extend the prefix only if every string matches there. So we compare column by column against strs[0] and return as soon as a string is too short or a character differs. No trie.

We use the first string strs[0] as a benchmark, and compare whether the i-th character of the subsequent strings is the same as the i-th character of strs[0]. If they are the same, we continue to compare the next character. Otherwise, we return the first i characters of strs[0].

If the traversal ends, it means that the first i characters of all strings are the same, and we return strs[0].

The time complexity is O(n × m), where n and m are the length of the string array and the minimum length of the strings, respectively. The space complexity is O(1).

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

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.