Longest Uploaded Prefix - Leetcode Solution

Problem Statement:

Given an array of strings, find the longest common prefix (LCP) amongst them. If there is no common prefix, return an empty string "".

Example 1:

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

Example 2:

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

Explanation: There is no common prefix among the input strings.

Solution:

To solve this problem, we can use the character-by-character matching approach. We start by comparing the first character of all the strings, then the second character of all the strings, and so on until we find a character mismatch or we reach the end of any of the strings. The common prefix is the substring up to the index of the mismatch.

To implement the above approach, we can follow the steps below:

1. Initialize the common prefix as the first string in the input array.
2. Iterate through the rest of the strings in the array.
3. For each string, compare its characters with the characters in the current common prefix string until there is a mismatch or we reach the end of the shortest one.
4. Update the common prefix to the substring up to the index of the mismatch.
5. Return the final common prefix.

Here is the Python code for the Longest Common Prefix problem:

def longestCommonPrefix(strs):
    if not strs:
        return ""
    common_prefix = strs[0]
    for s in strs[1:]:
        i = 0
        while i < len(common_prefix) and i < len(s) and common_prefix[i] == s[i]:
            i += 1
        common_prefix = common_prefix[:i]
        if not common_prefix:
            break
    return common_prefix

The time complexity of this solution is O(nm), where n is the number of strings in the array and m is the length of the shortest string. The space complexity is O(1) as we do not use any extra space.

1