Longest Common Prefix - CPP Solution

1. Introduction

In this blog post, we will explore how to find the longest common prefix string among an array of strings in C++. This is a common problem in string manipulation and is often encountered in coding interviews and problem-solving.

Problem

The task is to write a function that finds the longest common prefix string amongst an array of strings. If there is no common prefix, the function should return an empty string "".

2. Solution Steps

1. Start by checking if the array is empty. If so, return an empty string.

2. Initialize the prefix as the first string in the array.

3. Iterate through the strings in the array.

4. In each iteration, update the prefix by comparing it with the current string.

5. If the prefix becomes empty at any point, break out of the loop.

6. Return the longest common prefix found.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to find the longest common prefix among an array of strings
string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return ""; // Check for empty array

    string prefix = strs[0]; // Start with the first string as the prefix
    for (int i = 1; i < strs.size(); i++) {
        // Update the prefix by comparing with each string
        while (strs[i].find(prefix) != 0) {
            prefix = prefix.substr(0, prefix.length() - 1); // Reduce the prefix length
            if (prefix.empty()) return ""; // No common prefix found
        }
    }
    return prefix; // Return the longest common prefix
}

int main() {
    vector<string> strs = {"flower", "flow", "flight"};
    cout << "Longest common prefix: " << longestCommonPrefix(strs) << endl;
    return 0;
}

Output:

Longest common prefix: fl

Explanation:

1. The input array ["flower", "flow", "flight"] is processed to find the common prefix.

2. The first string "flower" is initially taken as the prefix.

3. The prefix is then compared and adjusted with each subsequent string.

4. The common prefix "fl" is found and returned as it is the longest prefix common to all strings in the array.

5. This approach efficiently finds the longest common prefix by iteratively refining the prefix.