Leetcode 14: Longest Common Prefix

1. Problem Statement (Simple Explanation):

You are given an array of strings strs.

You need to find the longest common prefix shared by all the strings.

• A prefix is a substring starting at index 0.

• If there is no common prefix, return the empty string "".

2. Examples:

Example 1:

Input: strs = ["flower","flow","flight"]

Output: "fl"

Explanation:

• All strings start with "fl":

• "flower" → "fl..."

• "flow" → "fl..."

• "flight" → "fl..."

• Next character differs ('o' vs 'i'), so longest common prefix is "fl".

Example 2:

Input: strs = ["dog","racecar","car"]

Output: ""

Explanation:

• First characters: 'd', 'r', 'c' → already different.

• So there is no common prefix → return "".

3. Approach 1 – Vertical Scanning (Character by Character):

Intuition:

Use the first string as a reference and compare character by character across all strings:

• For each index i in the first string:

• Check if all other strings have the same character at position i.

• If any string:

• is too short (i is out of bounds), or

• has a different character at i, then the common prefix ends just before i.

This is simple and efficient for the constraints.

Algorithm (Step-by-Step):

1. If strs is empty (not in constraints but good to handle), return "".

2. Let first = strs[0].

3. For each index i from 0 to len(first) - 1:

• Let c = first[i].

• For each other string strs[j] (j from 1 to n-1):

• If i is out of bounds for strs[j] (i.e., i >= len(strs[j])) or strs[j][i] != c:

• Return first[0:i] (prefix up to but not including index i).

4. If loop completes, entire first is a common prefix → return first.

Pseudo-code (Vertical Scanning):

Complexity:

Let:

• n = number of strings

• L = length of the shortest string L

• Time: in worst case, we compare each character for each string: O(n-L)

• Space: O(1) extra (ignoring output string).

4. Approach 2 – Horizontal Scanning (Prefix Shrinking):

You can mention briefly for your blog/video:

• Start with prefix = strs[0].

• For each string s in the array:

• While s does not start with prefix, remove the last character from prefix.

• If prefix becomes empty, return "".

• Return the final prefix.

This is also O(n*L)` and a common alternative.

For implementation, Approach 1 (vertical scanning) is clean and intuitive.

5. Java code:

6. C code:

7. C++ code:

8. Python code:

9. JavaScript code:

<<<PREV 

NEXT>>>