14. Longest Common Prefix

Intuition

The longest common prefix problem requires us to find the longest substring that appears at the start of all strings in a given array. The intuition here is to iteratively compare each string in the array to a potential prefix, shortening this prefix if necessary until it fits all strings.

Approach

1. Edge Case Handling: - If the input array strs is empty, return an empty string immediately.
2. Initialization: - Set the initial prefix to the first string in the array. This is the longest potential prefix we can have.
3. Iterative Comparison: - Iterate through each string in the array starting from the second string. - While the current string does not start with the current prefix: - Shorten the prefix by removing the last character. - If the prefix becomes empty, return an empty string as there is no common prefix.
4. Return Result: - After iterating through all strings, the remaining prefix is the longest common prefix.

Complexity

Time Complexity:

O(n * m), where n is the number of strings and m is the length of the longest string. In the worst case, each string comparison involves checking all characters in the prefix.

Space Complexity:

O(1) additional space is used, not counting the input and output.

This approach efficiently determines the longest common prefix by iteratively refining a potential prefix.

Code

C++

#include 
#include 

using namespace std;

class Solution {
public:
    string longestCommonPrefix(vector& strs) {
        if (strs.empty()) {
            return "";
        }

        string ans = strs[0];
        for (int i = 1; i < strs.size(); ++i) {
            while (strs[i].find(ans) != 0) {
                ans = ans.substr(0, ans.size() - 1);
                if (ans.empty()) {
                    return "";
                }
            }
        }

        return ans;
    }
};

Python

from typing import List

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        
        ans = strs[0]
        for i in range(1, len(strs)):
            while not strs[i].startswith(ans):
                ans = ans[:-1]
                if not ans:
                    return ""
        
        return ans

Java

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        String ans = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (!strs[i].startsWith(ans)) {
                ans = ans.substring(0, ans.length() - 1);
                if (ans.isEmpty()) {
                    return "";
                }
            }
        }
        
        return ans;
    }
}

JavaScript

var longestCommonPrefix = function(strs) {
    if (strs.length === 0) {
        return '';
    }
    let ans = strs[0];
    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(ans) !== 0) {
            ans = ans.substring(0, ans.length - 1);
            if (ans === '') {
                return '';
            }
        }
    }
    return ans;
};