Solution For Find The String With Lcp

Problem statement:

Given a list of strings, find the string with the longest common prefix (LCP).

Example 1:

Input: [“flower”,”flow”,”flight”] Output: “fl”

Example 2:

Input: [“dog”,”racecar”,”car”] Output: “”

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

Solution:

We can solve this problem by using the concept of Longest Common Prefix (LCP). For two strings, the LCP is the longest prefix that is common to both strings. For example, the LCP of “flower” and “flow” is “fl”.

To find the LCP of a list of strings, we can start with the first string and compare it with all the other strings in the list. For each comparison, we can update the LCP to be the common prefix of the two strings. If we find that the LCP becomes an empty string, we can stop comparing and return the empty string as the result since there is no common prefix among the input strings.

Let’s implement this algorithm in Python:

def longest_common_prefix(strs):
if not strs: # check if the input list is empty
return “”
lcp = strs[0] # initialize LCP to the first string in the list
for s in strs[1:]: # iterate over all other strings in the list
i = 0 # initialize index to 0
while i < len(lcp) and i < len(s): # compare the characters of the strings
if lcp[i] != s[i]: # if the characters do not match, break the loop
break
i += 1 # update index
lcp = lcp[:i] # update LCP to be the common prefix of the two strings
if not lcp: # if LCP becomes an empty string, return the empty string
return “”
return lcp # return the LCP

Let’s test the function with some examples:

print(longest_common_prefix([“flower”,”flow”,”flight”]))

Output: “fl”

print(longest_common_prefix([“dog”,”racecar”,”car”]))

Output: “” (empty string)

print(longest_common_prefix([“apple”,”ape”,”apricot”]))

Output: “ap”

print(longest_common_prefix([]))

Output: “” (empty string)

Time complexity: The time complexity of the above implementation is O(nm), where n is the number of strings in the input list and m is the length of the longest string. We are iterating over all the strings in the list and comparing each character of the strings until we find a mismatch or reach the end of the string. The worst-case scenario is when all the strings are the same and have length m, which results in a total of n(m+m) comparisons.

Space complexity: The space complexity of the above implementation is O(1), which is constant since we are only using some variables to store the input strings and the LCP. We are not using any additional space to solve this problem.

Step by Step Implementation For Find The String With Lcp

class Solution {
    public String lcp(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        int minLen = Integer.MAX_VALUE;
        for (String str : strs)
            minLen = Math.min(minLen, str.length());
        int low = 1, high = minLen;
        while (low <= high) {
            int middle = (low + high) / 2;
            if (isCommonPrefix(strs, middle))
                low = middle + 1;
            else
                high = middle - 1;
        }
        return strs[0].substring(0, (low + high) / 2);
    }
 
    private boolean isCommonPrefix(String[] strs, int len){
        String str1 = strs[0].substring(0,len);
        for (int i = 1; i < strs.length; i++)
            if (!strs[i].startsWith(str1))
                return false;
        return true;
    }
}

def findLCP(s, i, j): 
  
    while (i != j): 
        if (s[i] < s[j]): 
            j -= 1
  
        else: 
            i += 1
  
    return s[i:] 
  

s = "acbdfghy"
ans = findLCP(s, 0, len(s)-1) 
print(ans)

var lcp = function(strs) {
    if (strs.length == 0) return "";
    
    // sort the array
    strs.sort();
    
    // take the first two strings and find the longest common prefix
    var prefix = findLCP(strs[0], strs[1]);
    
    // check if the prefix is the longest common prefix for the entire array
    for (var i = 2; i < strs.length; i++) {
        // if the prefix is not a prefix for the current string in the array,
        // then it is not the longest common prefix for the entire array
        if (!isPrefix(strs[i], prefix)) {
            return "";
        }
    }
    
    return prefix;
};

// finds the longest common prefix of two strings
var findLCP = function(str1, str2) {
    var minLength = Math.min(str1.length, str2.length);
    
    // find the longest common prefix of the two strings
    for (var i = 0; i < minLength; i++) {
        if (str1.charAt(i) != str2.charAt(i)) {
            return str1.substring(0, i);
        }
    }
    
    // if we reach here, that means the entire str1 is a prefix of str2
    // or the entire str2 is a prefix of str1
    return str1.substring(0, minLength);
};

// checks if str1 is a prefix of str2
var isPrefix = function(str1, str2) {
    for (var i = 0; i < str2.length; i++) {
        if (str1.charAt(i) != str2.charAt(i)) {
            return false;
        }
    }
    
    return true;
};

class Solution {
public:
    string longestCommonPrefix(vector& strs) {
        // check for empty vector
        if (strs.empty()) {
            return "";
        }
        // find shortest string in vector
        int minLen = strs[0].length();
        for (string s : strs) {
            minLen = min(minLen, (int)s.length());
        }
        // loop through each character of the shortest string
        // and compare it with the corresponding character
        // of each other string in the vector
        // if they are not equal, return the substring up to that point
        for (int i = 0; i < minLen; i++) {
            char c = strs[0][i];
            for (string s : strs) {
                if (s[i] != c) {
                    return s.substr(0, i);
                }
            }
        }
        // if all characters are equal, return the shortest string
        return strs[0].substr(0, minLen);
    }
};

public class Solution { 
    public string LongestCommonPrefix(string[] strs) { 
        if (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.Length == 0) return ""; 
            }        
        return prefix; 
    } 
}