Longest Common Prefix in an Array of Strings

Given an array of strings, find the longest common prefix among all strings. If there is no common prefix, return an empty string.

Input/Output Examples

plaintext
Example 1:
Input:
strs = ["flower", "flow", "flight"]
Output: "fl"
Explanation: The longest common prefix among all the strings is "fl".

Example 2:
Input:
strs = ["dog", "racecar", "car"]
Output: ""
Explanation: There is no common prefix among the strings, so the output is an empty string.

Example 3:
Input:
strs = ["interspace", "internet", "internal"]
Output: "inte"
Explanation: The longest common prefix among all the strings is "inte".

Approach to Find Longest Common Prefix in an array of strings

  1. Handle Edge Cases:
    • If the list is empty, return an empty string.
    • If the list has only one string, return that string since it is the longest common prefix with itself.
  2. Compare Characters of Each String:
    • Use the first string as a reference and compare its characters with those at the same position in the other strings.
    • Continue comparing until you find a mismatch or reach the end of one of the strings.
  3. Return the Common Prefix:
    • When a mismatch is found, return the prefix up to that position.
    • If no mismatch is found after checking all strings, the reference string is the longest common prefix.

C++ Program to Find Longest Common Prefix in an array of strings

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

// Function to find the longest common prefix
string longestCommonPrefix(const vector<string>& strs) {
    if (strs.empty()) return "";

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

    return prefix;
}

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

Java Program to Find Longest Common Prefix in an array of strings

java
public class LongestCommonPrefix {

    // Function to find the longest common prefix
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";

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

        return prefix;
    }

    public static void main(String[] args) {
        String[] strs = {"dog", "racecar", "car"};
        System.out.println("Longest Common Prefix: " + longestCommonPrefix(strs));
    }
}

Python Program to Find Longest Common Prefix in an array of strings

python
# Function to find the longest common prefix
def longest_common_prefix(strs):
    if not strs:
        return ""

    prefix = strs[0]
    for s in strs[1:]:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""

    return prefix

# Example usage
if __name__ == "__main__":
    strs = ["interspace", "internet", "internal"]
    print("Longest Common Prefix:", longest_common_prefix(strs))
  • Time Complexity: O(n * m), where n is the number of strings and m is the length of the shortest string. This complexity is due to the comparison of each character in the strings up to the length of the shortest string.
  • Space Complexity: O(1), as the algorithm only requires a constant amount of additional space to store the prefix and temporary variables.

DSA

6804

808

Related Articles