Longest Common Prefix In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement: Longest Common Prefix

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

Note:

• All strings in the array will have at least one character.
• You may assume all strings consist of only lowercase English letters.

Example:

Input:

pythonCopy code["flower", "flow", "flight"]

Output:

pythonCopy code"fl"

Input:

pythonCopy code["dog", "racecar", "car"]

Output:

pythonCopy code""

Approach:

There are several methods to solve this problem, but the most common ones include:

1. Vertical Scanning:
   • Compare the characters of each string column by column (i.e., character by character in the same position across all strings).
   • Stop when you find a mismatch or reach the end of one of the strings.
2. Horizontal Scanning:
   • Start by taking the first string as the prefix, and then compare it with each subsequent string.
   • Gradually reduce the length of the prefix until it matches all strings.
3. Divide and Conquer:
   • Divide the array into two halves, recursively find the LCP of the two halves, and merge the results.
   • This approach uses a divide-and-conquer strategy similar to the merge sort.
4. Binary Search:
   • Perform binary search on the string lengths, checking whether the first mid characters of all strings match.
5. Trie (Prefix Tree):
   • Insert all the strings into a Trie, and then find the longest common prefix by traversing the Trie from the root.

For simplicity and efficiency, we will use the Horizontal Scanning approach here.

Approach (Horizontal Scanning):

1. Initialize the Prefix:
   • Start with the first string as the prefix.
2. Iterate Through Strings:
   • Compare the current prefix with each string in the list.
   • If the current string does not start with the prefix, reduce the prefix by chopping off characters from the end until a match is found.
3. Termination:
   • When we have processed all the strings, the remaining prefix is the longest common prefix.
4. Edge Case:
   • If there is no common prefix, the result should be an empty string.

Time Complexity:

• Time Complexity: O(S)O(S)O(S), where SSS is the sum of all characters in all strings. This is because in the worst case, we compare each character of each string.
• Space Complexity: O(1)O(1)O(1), since we only store the prefix.

Code Implementation

C Code:

#include <stdio.h>
#include <string.h>

char* longestCommonPrefix(char **strs, int strsSize) {
    if (strsSize == 0) return "";
    
    // Initialize the prefix as the first string
    char *prefix = strs[0];
    
    // Compare with each string
    for (int i = 1; i < strsSize; i++) {
        // Keep reducing the prefix while it doesn't match the start of strs[i]
        while (strncmp(prefix, strs[i], strlen(prefix)) != 0) {
            // Reduce the prefix by one character from the end
            prefix[strlen(prefix) - 1] = '\0';
        }
    }
    
    return prefix;
}

int main() {
    char* strs[] = {"flower", "flow", "flight"};
    int strsSize = 3;
    printf("Longest Common Prefix: %s\n", longestCommonPrefix(strs, strsSize));  // Output: "fl"
    return 0;
}

C++ Code:

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

string longestCommonPrefix(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.size() - 1);
        }
    }
    
    return prefix;
}

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

Java Code:

public class Solution {
    public 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);
            }
        }
        
        return prefix;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] strs = {"flower", "flow", "flight"};
        System.out.println("Longest Common Prefix: " + solution.longestCommonPrefix(strs));  // Output: "fl"
    }
}

Python Code:

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

# Example Usage
strs = ["flower", "flow", "flight"]
print("Longest Common Prefix:", longestCommonPrefix(strs))  # Output: "fl"

C# Code:

using System;

public class Solution {
    public string LongestCommonPrefix(string[] strs) {
        if (strs.Length == 0) return "";
        
        string prefix = strs[0];
        
        foreach (var str in strs) {
            while (!str.StartsWith(prefix)) {
                prefix = prefix.Substring(0, prefix.Length - 1);
                if (prefix == "") return "";
            }
        }
        
        return prefix;
    }

    public static void Main() {
        Solution solution = new Solution();
        string[] strs = {"flower", "flow", "flight"};
        Console.WriteLine("Longest Common Prefix: " + solution.LongestCommonPrefix(strs));  // Output: "fl"
    }
}

JavaScript Code:

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

console.log(longestCommonPrefix(["flower", "flow", "flight"]));  // Output: "fl"

Explanation:

1. Initialize Prefix: The first string is taken as the initial prefix.
2. Iterate Through Strings: For each string, check if the prefix matches the beginning of the string. If not, shorten the prefix by removing the last character until a match is found or the prefix becomes empty.
3. Return Prefix: If the loop finishes and the prefix is not empty, it will be the longest common prefix. If the prefix becomes empty during the process, return an empty string.

Edge Cases:

1. Empty List: If the input list is empty, the function should return an empty string.
2. No Common Prefix: If no common prefix exists, the function should return an empty string.
3. Single String: If there is only one string, that string is the longest common prefix.

---

Summary:

• Time Complexity: O(S)O(S)O(S), where SSS is the sum of the lengths of all strings in the input list. In the worst case, we are comparing all characters in each string.
• Space Complexity: O(1)O(1)O(1), as the space used does not depend on the input size (only the prefix is stored).