LeetCode #14 - Longest Common Prefix

Hello fellow devs πŸ‘‹! Today we will discuss another LeetCode problem.

Problem Statement

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 "".

Constraints

  • 0 ≀ strs.length ≀ 200
  • 0 ≀ strs[i].length ≀ 200
  • strs[i] consists of only lower-case English letters.

Examples

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.

Analysis

As per the question, we will be given an array of some strings which can be of varying lengths. We only have to find first n characters which appear in each string between the indices 0 and n - 1.

It is clear that the common characters cannot be more than the length of the shortest string of all the given strings. Therefore, we will first find the shortest string amongst all strings and check maximum characters of it are present in all the other strings.

If not a single character is present in all the other string, we will return an empty string.

Approach

The approach is pretty simple -

  1. First we will find the shortest string and its length.
  2. Secondly, we will take the first string and match its each character one by one with all the other strings.
  3. As soon as we encounter a character which does not match, we will break out of loop.

Time Complexity

If n is the length of the array and m is the length of the shortest string, the worst case time complexity will be O(m Γ— n).

Space Complexity

Since we are not using any internal data structure for intermediate computations, the space complexity will be O(1).

Code

Java

public class LongestCommonPrefix {

    public String longestCommonPrefix(String[] strs) {
        // Longest common prefix string
        StringBuilder longestCommonPrefix = new StringBuilder();
        // Base condition
        if (strs == null || strs.length == 0) {
            return longestCommonPrefix.toString();
        }
        // Find the minimum length string from the array
        int minimumLength = strs[0].length();
        for (int i = 1; i < strs.length; i++) {
            minimumLength = Math.min(minimumLength, strs[i].length());
        }
        // Loop for the minimum length
        for (int i = 0; i < minimumLength; i++) {
            // Get the current character from first string
            char current = strs[0].charAt(i);
            // Check if this character is found in all other strings or not
            for (String str : strs) {
                if (str.charAt(i) != current) {
                    return longestCommonPrefix.toString();
                }
            }
            longestCommonPrefix.append(current);
        }
        return longestCommonPrefix.toString();
    }
}

Python

def longestCommonPrefix(strs: List[str]) -> str:
    # Longest common prefix string
    lcp = ""
    # Base condition
    if strs is None or len(strs) == 0:
        return lcp
    # Find the minimum length string from the array
    minimumLength = len(strs[0])
    for i in range(1, len(strs)):
        minimumLength = min(minimumLength, len(strs[i]))
    # Loop until the minimum length
    for i in range(0, minimumLength):
        # Get the current character from the first string
        current = strs[0][i]
        # Check if this character is found in all other strings or not
        for j in range(0, len(strs)):
            if strs[j][i] != current:
                return lcp
        lcp += current
    return lcp

JavaScript

var longestCommonPrefix = function (strs) {
    // Longest common prefix string
    let longestCommonPrefix = "";
    // Base condition
    if (strs == null || strs.length == 0) {
        return longestCommonPrefix;
    }
    // Find the minimum length string from the array
    let minimumLength = strs[0].length;
    for (let i = 1; i < strs.length; i++) {
        minimumLength = Math.min(minimumLength, strs[i].length);
    }
    // Loop for the minimum length
    for (let i = 0; i < minimumLength; i++) {
        // Get the current character from first string
        let current = strs[0][i];
        // Check if this character is found in all other strings or not
        for (let j = 0; j < strs.length; j++) {
            if (strs[j][i] != current) {
                return longestCommonPrefix;
            }
        }
        longestCommonPrefix += current;
    }
    return longestCommonPrefix;
};

Kotlin

fun longestCommonPrefix(strs: Array<String>): String {
    // Longest common prefix string
    val longestCommonPrefix = StringBuilder()
    // Base condition
    if (strs.isEmpty()) {
        return longestCommonPrefix.toString()
    }
    // Find the minimum length string from the array
    var minimumLength = strs[0].length
    for (i in 1 until strs.size) {
        minimumLength = minimumLength.coerceAtMost(strs[i].length)
    }
    // Loop for the minimum length
    for (i in 0 until minimumLength) {
        // Get the current character from first string
        val current = strs[0][i]
        // Check if this character is found in all other strings or not
        for (str in strs) {
            if (str[i] != current) {
                return longestCommonPrefix.toString()
            }
        }
        longestCommonPrefix.append(current)
    }
    return longestCommonPrefix.toString()
}

Complete Code

Conclusion

Congratulations πŸ‘! We have solved another problem from LeetCode.

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork πŸ”ͺ and star ⭐ it.

Till next time… Happy coding πŸ˜„ and Namaste πŸ™!


Created and maintained by@Anirudh Sharma
I love to learn and share. Hence, this site has no ads, no affiliation links, or any BS. If you like what you see, give me a thumbs up.

GitHub iconMedium iconTwitter iconFacebook iconLinkedIn iconStackoverflow icon