Skip to main content

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>>>

Comments

Post a Comment