Solution For Longest Common Prefix

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

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 comparing the first character of each string and then moving on to the next character until we reach a character that is not common in all the strings or the end of any string is reached.

First, we check if the length of the input string array is 0 or not. If it is 0, then we return an empty string as there is no common prefix. If the input array has only one string, then we return that string as the common prefix.

We start with the first string in the input array and loop through its characters. For each character, we compare it with the first character of all other strings in the array. If we find a mismatch, then we return the substring of the first string till the position of the mismatch character as the common prefix. If we reach the end of the first string without finding any mismatches, then we add the character to the common prefix and move on to the next character of the first string.

Here is the Python code implementing the above algorithm:

def longestCommonPrefix(strs: List[str]) -> str:
if len(strs) == 0:
return “”
if len(strs) == 1:
return strs[0] prefix = “”
for i in range(len(strs[0])):
char = strs[0][i] for j in range(1, len(strs)):
if i >= len(strs[j]) or char != strs[j][i]:
return prefix
prefix += char
return prefix

Complexity Analysis:
Time complexity: O(NM), where N is the length of the input string array and M is the length of the longest string in the array. In the worst case, we have to compare all the characters of all the strings, hence NM.

Space complexity: O(1), we are not using any extra space for the algorithm.

Step by Step Implementation For Longest Common Prefix

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        // check for empty array
        if (strs.length == 0) {
            return "";
        }
        
        // find shortest string
        int minLen = Integer.MAX_VALUE;
        for (String str : strs) {
            minLen = Math.min(minLen, str.length());
        }
        
        // iterate through all strings to find longest common prefix
        for (int i = 0; i < minLen; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0].substring(0, minLen);
    }
}

def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        shortest = min(strs,key=len)
        for i, ch in enumerate(shortest):
            for other in strs:
                if other[i] != ch:
                    return shortest[:i]
        return shortest

var longestCommonPrefix = function(strs) {
    // Edge case: if strs is empty, return an empty string
    if (strs.length === 0) {
        return "";
    }
    
    // We will take the first string in the array as our starting point
    let prefix = strs[0];
    
    // Loop through the array, starting at the second string
    for (let i = 1; i < strs.length; i++) {
        // As long as the current string doesn't start with the prefix,
        // we will remove the last character from the prefix until it does
        // or until the prefix is empty
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.substring(0, prefix.length - 1);
            
            // If the prefix is empty, that means there is no common prefix
            // among all the strings, so we can return an empty string
            if (prefix === "") {
                return "";
            }
        }
    }
    
    // If we get to this point, that means there is a common prefix among
    // all the strings, so we can return it
    return prefix;
};

One solution to the longest common prefix problem is to use a trie data structure. In a trie, each node represents a prefix of a string. The root node represents the empty string, and each child node represents a single character in the string. To find the longest common prefix, we can simply traverse the trie from the root node to the deepest child node. The depth of the deepest child node is the length of the longest common prefix.

Here is some pseudocode for a trie-based solution to the longest common prefix problem:

TrieNode root = new TrieNode();

// Insert each string into the trie

for (String str : strs) {

TrieNode curr = root;

for (char c : str.toCharArray()) {

if (!curr.children.containsKey(c)) {

curr.children.put(c, new TrieNode());

}

curr = curr.children.get(c);

}

}

// Find the depth of the deepest child node

int maxDepth = 0;

for (TrieNode child : root.children.values()) {

maxDepth = Math.max(maxDepth, child.depth);

}

// The longest common prefix is the prefix represented by the deepest child node

return strs[0].substring(0, maxDepth);

class Solution {
    public string LongestCommonPrefix(string[] strs) {
        // check for empty array
        if (strs.Length == 0) return "";
        
        // set first word as prefix
        string prefix = strs[0];
        
        // loop through array, starting at the second word
        for (int i = 1; i < strs.Length; i++) {
            // while the current word doesn't start with the prefix
            // and the prefix isn't empty
            while (strs[i].IndexOf(prefix) != 0 && prefix != "") {
                // remove the last character from the prefix
                prefix = prefix.Substring(0, prefix.Length - 1);
            }
        }
        
        return prefix;
    }
}