codingcircle » 14. Longest Common Prefix

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

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters if it is non-empty.

Problem Description

The goal of this problem is to write a function that takes an array of strings and returns the longest common prefix that is shared among all the strings. The common prefix is the starting part of the strings that is identical for all of them. For example, if the input is ["flower","flow","flight"], the longest common prefix is "fl", since it’s the beginning part that all the strings have in common. If the strings have no common prefix, the function should return an empty string "".

The function will need to check the strings in the array and compare them to find the longest sequence of characters that is present at the start of each string. This problem requires an efficient way to compare the strings and determine the common prefix.

Intuition

When trying to find a common pattern among a set of items, a logical step is to begin by looking at the first item and then comparing it with subsequent items. Similarly, in the case of finding the longest common prefix, it makes sense to start with the first string in the array and compare its characters one by one with the characters at the corresponding positions in the other strings.

To achieve this, we perform the following steps:

If the array is empty, there can’t be a common prefix, so we would return an empty string. However, if the array contains at least one string, then we consider the entire first string as the initial longest common prefix candidate.
Next, we iterate through the characters of the first string. For each character, we check if the same character index in every other string in the array is the same character. To do this, we have an inner loop that compares the character at index i of strs[0] with the character at index i of each subsequent string (strs[1:]).
If at any point the comparison fails because we’ve reached the end of one of the other strings, or the characters do not match, we’ve found the end of the common prefix. We can immediately return the substring of the first string up to (but not including) character i.
If the inner loop completes without finding a mismatch, it means that the current character is part of the common prefix for all strings checked so far. We continue moving to the next character.
If we successfully compare all characters in the first string without finding a mismatch, then the entire first string is the common prefix. In this case, the simple conclusion is that there is no shorter prefix than the first string itself, so we return it.

By following this comparison logic, we ensure that as soon as a discrepancy is found, we do not waste any further time checking additional characters, thereby optimizing the function for better performance.

Solution Approach

The solution employs a simple yet effective algorithm that involves iterating over each character position of the strings in the array and comparing them to find the longest common prefix.

Here’s how the implementation works step by step:

We start by looking at the first string in the array, strs[0], and assume that it could be the potential longest common prefix. We use this string as a reference to compare with all other strings.
We then enter a for-loop, which iterates over the character indices of the first string. The variable i represents the index of the character we are currently checking.
Within this loop, we initiate another for-loop that iterates through the remaining strings in the array—strs[1:].
For each string s in this inner loop, we perform two checks: a. If the current index i is greater than or equal to the length of the string s, this means we have reached the end of this string, and thus, it cannot have a longer common prefix. b. If the character at index i of the string s does not match the character at the same index in strs[0], this indicates that the current character does not form part of a common prefix.
If either condition in the inner loop is true, we have identified the end of the common prefix, and we return the substring of the first string from index 0 to i, using s[:i]. This is the longest common prefix found up to that point.
If the inner loop completes without triggering the return statement, it means that the current character at index i is shared by all strings checked, and thus, the loop continues to the next character.
If the outer loop completes without any return, this indicates that every character of the first string strs[0] is part of the common prefix for all strings. Therefore, we can safely return strs[0] as the longest common prefix.

This algorithm essentially implements a character-by-character comparison, making use of string slicing for efficient checking and early stopping as soon as a mismatch is found. No additional data structures are needed, thus the space complexity is kept to a minimum.

The early return mechanism greatly improves performance by terminating the comparison as soon as the longest common prefix is established, without further unnecessary comparisons.

The procedure can be visualized as lining up all the strings vertically and scanning down the columns (indices). Once a discrepancy is found in any column, we know that the common prefix can only be as long as the last column without discrepancies.

Example Walkthrough

To illustrate the solution approach, let’s take an example array of strings: ["cardboard", "cart", "carrot", "carbon"]. We want to find the longest common prefix among these strings.

Initial Assumption: We start with the assumption that the first string “cardboard” is our longest common prefix candidate.
Character-by-Character Comparison:
- We start comparing the first character ‘c’ from “cardboard” with the first character of all the other strings. All strings have ‘c’ as their first character.
- Next, we compare the second character ‘a’ from “cardboard” with the second character of the other strings. All strings have ‘a’ as their second character.
- We continue to the third character ‘r’ from “cardboard” and compare it with the third character of the other strings. All strings have ‘r’ as well.
Mismatch and Early Termination:
- Now we move to the fourth character ‘d’ from “cardboard”. However, when we compare it with the fourth character of “cart”, we find that it is ‘t’ and not ‘d’. This is a mismatch.
- Since “cart” has no more characters to compare (it is shorter than “cardboard”), this is our signal to stop.
Returning the Result: At this point, we found that all strings share the prefix “car”. We return this prefix as it is the longest common prefix that can be formed from all given strings.

The longest common prefix based on our algorithm is “car”. This was determined efficiently by stopping comparisons once the first mismatch occurred or a string ended, ensuring no extra work was done.

Solution Implementation

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        // If the input vector is empty, return an empty string
        if (strs.empty()) return "";

        string pref = strs[0];  // Set the first string as the initial prefix
        int prefLen = pref.length();  // Get the length of the initial prefix

        // Iterate through the remaining strings in the vector
        for (int i = 1; i < strs.size(); i++) {
            string s = strs[i];  // Get the current string

            // While the prefix length is greater than the current string's length or 
            // the prefix does not match the start of the current string
            while (prefLen > s.length() || pref != s.substr(0, prefLen)) {
                prefLen--;  // Decrease the prefix length
                if (prefLen == 0) {  // If no common prefix exists
                    return "";  // Return an empty string
                }
                pref = pref.substr(0, prefLen);  // Update the prefix to match the current length
            }
        }

        return pref;  // Return the longest common prefix found
    }
};

Copied!

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // If the input array is null or empty, return an empty string
        if (strs == null || strs.length == 0) return "";
        
        String pref = strs[0];  // Set the first string as the initial prefix
        int prefLen = pref.length();  // Get the length of the initial prefix

        // Loop through the remaining strings in the array
        for (int i = 1; i < strs.length; i++) {
            String s = strs[i];  // Get the current string

            // While the prefix length is greater than the current string's length or 
            // the prefix does not match the start of the current string
            while (prefLen > s.length() || !pref.equals(s.substring(0, prefLen))) {
                prefLen--;  // Decrease the prefix length
                if (prefLen == 0) {  // If no common prefix exists
                    return "";  // Return an empty string
                }
                pref = pref.substring(0, prefLen);  // Update the prefix to match the current length
            }
        }

        return pref;  // Return the longest common prefix found
    }
}

Copied!

class Solution:
 def longestCommonPrefix(self, strs: List[str]) -> str:
     pref = strs[0]  # Set the first string as the initial prefix
     pref_len = len(pref)  # Get the length of the initial prefix
     # Loop through the remaining strings in the list
     for s in strs[1:]:
         # While the prefix doesn't match the start of the current string
         while pref != s[0:pref_len]:
             pref_len -= 1  # Decrease the prefix length
             if pref_len == 0:  # If no common prefix exists
                 return ""  # Return an empty string
             
             pref = pref[0:pref_len]  # Update the prefix to match the current length
     
     return pref  # Return the longest common prefix found

Copied!

char* longestCommonPrefix(char** strs, int strsSize) {
    // If the input array is empty, return an empty string
    if (strsSize == 0) return "";

    char* prefix = strs[0];  // Set the first string as the initial prefix

    // Loop through the remaining strings in the array
    for (int i = 1; i < strsSize; i++) {
        int j = 0;  // Initialize index to compare characters
        
        // Compare characters of the current string with the prefix
        // Stop when characters don't match or we reach the end of either string
        while (prefix[j] && strs[i][j] && prefix[j] == strs[i][j]) {
            j++;  // Move to the next character
        }

        prefix[j] = '\0';  // Truncate the prefix to the matching portion
    }

    return prefix;  // Return the longest common prefix found
}

Copied!

public class Solution 
{
    public string LongestCommonPrefix(string[] strs) 
    {
        // Sort the array of strings
        Array.Sort(strs);
        
        // Use StringBuilder to store the common prefix
        StringBuilder sb = new StringBuilder();
        
        // Get the first and last strings in the sorted array
        string first = strs[0];
        string last = strs[strs.Length - 1];
        
        // Compare characters of the first and last strings
        for (int i = 0; i < Math.Min(first.Length, last.Length); i++)
        {
            if (first[i] != last[i])
            {
                return sb.ToString();
            }
            sb.Append(first[i]);
        }
        
        return sb.ToString();
    }
}

Copied!

var longestCommonPrefix = function(strs) {
    let pref = strs[0];  // Set the first string as the initial prefix
    let prefLen = pref.length;  // Get the length of the initial prefix

    // Loop through the remaining strings in the array
    for (let i = 1; i < strs.length; i++) {
        let s = strs[i];  // Get the current string
        // While the prefix doesn't match the start of the current string
        while (pref !== s.substring(0, prefLen)) {
            prefLen--;  // Decrease the prefix length
            if (prefLen === 0) {  // If no common prefix exists
                return "";  // Return an empty string
            }
            pref = pref.substring(0, prefLen);  // Update the prefix to match the current length
        }
    }

    return pref;  // Return the longest common prefix found    
};

Copied!

function longestCommonPrefix(strs: string[]): string {
  let prefix = strs[0];  // Set the first string as the initial prefix

  // Loop through the remaining strings in the array
  for (let i = 1; i < strs.length; i++) {
    // While the current string does not start with the prefix, reduce the prefix by removing the last character
    while (!strs[i].startsWith(prefix)) {
      prefix = prefix.slice(0, -1);  // Remove the last character from the prefix
    }

    // If the prefix becomes an empty string, return it immediately as no common prefix exists
    if (prefix === '') {
      return prefix;
    }
  }

  return prefix;  // Return the longest common prefix found
};

Copied!

 class Solution {
    /**
     * @param String[] $strs
     * @return String
     */
    function longestCommonPrefix($strs) {
        $prefix = "";  // Initialize the prefix as an empty string
        sort($strs, SORT_STRING);  // Sort the array of strings alphabetically
        $first = $strs[0];  // Get the first string in the sorted array
        $last = end($strs);  // Get the last string in the sorted array
        $length = strlen($first);  // Get the length of the first string
        
        // Iterate through the characters of the first string
        for ($i = 0; $i < $length; $i++) {
            // If the characters at the same position in the first and last string match
            if (substr($first, $i, 1) === substr($last, $i, 1)) {
                $prefix .= substr($first, $i, 1);  // Add the matching character to the prefix
            }
            else { 
                return $prefix;  // If characters don't match, return the prefix found so far
            }
        }        

        return $prefix;  // Return the longest common prefix found
    }
}

Copied!

class Solution {
    // Function to find the longest common prefix from an array of strings
    func longestCommonPrefix(_ strs: [String]) -> String {
        
        // If the input array is empty, return an empty string
        if strs.isEmpty { return "" }
        
        // Initialize 'common' to be the first string in the array
        var common = strs[0]
        
        // Loop through each string in the array
        for ch in strs {
            // While the current string does not have the 'common' prefix
            while !ch.hasPrefix(common) {
                // Trim the last character from 'common' to shorten the prefix
                common = String(common.dropLast())
            }
        }
        
        // Return the longest common prefix found
        return common
    }
}

Copied!

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        // If list has only one item it is the longest prefix.
        if(strs.size == 1) return strs[0]
        
        // Find the length of shortest string in array.
        var min = Integer.MAX_VALUE
        for(s in strs){
            min = Math.min(min, s.length)
        }
        
        for(i in 0 until min){
            val char = strs[0][i]
            for(s in strs){
                // When a mismatch is found return the substring. (i.e. ["abc","abf"] c and f in this case)
                if(s[i] !== char){
                    return s.substring(0, i)
                }
            }
        }
    
        return strs[0].substring(0, min)
    }
}

Copied!

class Solution {
  String longestCommonPrefix(List strs) {
  if (strs.isEmpty) return ""; // If list is empty, return empty

  // Take the first word as the beginning
  String prefix = strs[0];

  // Compare with other words
  for (int i = 1; i < strs.length; i++) {
    // Trim until current word matches `prefix`
    while (!strs[i].startsWith(prefix)) {
      prefix = prefix.substring(0, prefix.length - 1);
      if (prefix.isEmpty) return ""; // If prefix is completely empty, return
    }
  }
    return prefix;
    }
}

Copied!

func longestCommonPrefix(strs []string) string {
    // Start with the first string in the array as the initial 'str'
    str := strs[0]
    
    // Loop through the rest of the strings in the array to find the shortest one
    for i := 1; i < len(strs); i++ {
        // If a string is shorter than the current 'str', update 'str' to be that string
        if len(strs[i]) < len(str) {
            str = strs[i]
        }
    }
    
    // Initialize a buffer to store the common prefix
    var prefix bytes.Buffer
    
    // Iterate through each character of 'str'
    for i := 0; i < len(str); i++ {
        // Flag to check if the character at index i is common across all strings
        to_add := true
        
        // Loop through each string to check if the current character matches
        for j := 0; j < len(strs); j++ {
            if strs[j][i] != str[i] {
                to_add = false
            }
        }
        
        // If the character is common, add it to the prefix buffer
        if to_add {
            prefix.WriteByte(str[i])
        } else {
            // If any mismatch is found, break the loop as no longer common
            break
        }
    }
    
    // Return the common prefix as a string
    return prefix.String()
}

Copied!

Time and Space Complexity

The time complexity of the code is O(n * m), where n is the number of strings in the given list, and m represents the length of the shortest string in the list. Each character of the shortest string is iterated n times to check if it is a common prefix among all the strings.

The space complexity of the solution is O(1), as it does not allocate additional space proportional to the input size, using only a few variables to perform the checks and return the result.

Leave a Reply