Longest Common Prefix easy

Problem Statement

Write a function to find the longest common prefix string amongst an array of strings.

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.

Steps:

1. Handle Empty Input: If the input array strs is empty, return an empty string. This avoids potential errors.

2. Initialize Prefix: Assume the first string in the array is the longest common prefix initially.

3. Iterate and Compare: Iterate through the remaining strings in the array. For each string:

   • Compare its characters with the current prefix, character by character.
   • If a mismatch is found, shorten the prefix to the characters before the mismatch.
   • If a string is shorter than the current prefix, shorten the prefix to match the length of the shorter string.

4. Return Prefix: After iterating through all strings, the prefix variable will hold the longest common prefix. Return this prefix.

Explanation:

The algorithm uses a simple iterative approach. It starts with the assumption that the first string is the longest common prefix. Then, it compares this prefix against each subsequent string. Whenever a mismatch is found, the prefix is truncated to the point of the mismatch. This process ensures that only the characters common to all strings are retained in the prefix.

Code:

#include <string>
#include <vector>

using namespace std;

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) {
        return "";
    }

    string prefix = strs[0]; // Initialize prefix with the first string

    for (size_t i = 1; i < strs.size(); ++i) {
        size_t j = 0;
        while (j < prefix.length() && j < strs[i].length() && prefix[j] == strs[i][j]) {
            j++;
        }
        prefix = prefix.substr(0, j); // Shorten the prefix if a mismatch is found
        if(prefix.empty()) return ""; //optimization: if prefix becomes empty, no need to continue
    }

    return prefix;
}

Complexity:

• Time Complexity: O(S), where S is the sum of all characters in all strings. In the worst case, we might have to iterate through all characters of all strings.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size. The space used by the prefix string is not considered extra space because it's using space already allocated to the input.