LeetCode Challenge: 14. Longest Common Prefix - JavaScript Solution 🚀

#javascript #programming #leetcode #interview

Top Interview 150

The Longest Common Prefix problem is a classic string manipulation challenge that tests your ability to identify shared patterns among strings. Let’s break down LeetCode 14: Longest Common Prefix and solve it in JavaScript.

🚀 Problem Description

Given an array of strings strs, return the longest common prefix among all strings in the array.

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

💡 Examples

Example 1

Input: strs = ["flower","flow","flight"]  
Output: "fl"  
Explanation: The first two letters "fl" are common to all strings.

Example 2

Input: strs = ["dog","racecar","car"]  
Output: ""  
Explanation: No common prefix exists among the input strings.

🏆 JavaScript Solution

We’ll take a horizontal scanning approach, where we iteratively compare the prefix of one string with the next string, updating the common prefix as we go.

Implementation

var longestCommonPrefix = function(strs) {
    if (!strs.length) return "";

    let prefix = strs[0];
    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.slice(0, -1);
            if (prefix === "") return "";
        }
    }

    return prefix;
};

🔍 How It Works

Start with the First String:
- Use the first string as the initial prefix.
Iteratively Check Strings:
- Compare the current prefix with each string.
- If the prefix does not match the start of the string, shorten it by removing the last character until it matches.
Return the Prefix:
- Once all strings are checked, the remaining prefix is the longest common prefix.

🔑 Complexity Analysis

> Time Complexity: O(S), where S is the sum of all characters in the array.
- In the worst case, every character in the array is compared.
> Space Complexity: O(1), as no additional data structures are used.

📋 Dry Run

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

Output: "fl"

Alternative Solution: Vertical Scanning

Instead of comparing strings one by one, you can compare characters at each index across all strings.

var longestCommonPrefix = function(strs) {
    if (!strs.length) return "";

    for (let i = 0; i < strs[0].length; i++) {
        const char = strs[0][i];

        for (let j = 1; j < strs.length; j++) {
            if (i >= strs[j].length || strs[j][i] !== char) {
                return strs[0].slice(0, i);
            }
        }
    }

    return strs[0];
};

🔑 Complexity Analysis (Vertical Scanning)

> Time Complexity: O(S), same as horizontal scanning.
> Space Complexity: O(1).

✨ Pro Tips for Interviews

Clarify constraints: Confirm whether the array can be empty or contain strings of varying lengths.
Discuss edge cases:
- Empty string array ([] → "").
- Single string input (["single"] → "single").
- Strings with no common prefix (["dog", "cat"] → "").
Explain your choice of approach: Highlight the difference between horizontal and vertical scanning.