Longest Common Prefix Leetcode Solution

Problem Statement

The Longest Common Prefix LeetCode Solution – “Longest Common Prefix” states that given an array of strings. We need to find the longest common prefix among these strings. If there doesn’t exist any prefix, return an empty string.

Example:

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

Output: "fl"

Explanation:

• “fl” is the longest common prefix among all the three strings.

Input:  strs = ["dog","racecar","car"]

Output: ""

Explanation:

• The first character of all the strings is different, there is no common prefix.

Approach

Idea:

1. The main idea to solve this problem is to use two loops.
2. We’ll pick the first string and find the longest common prefix.
3. For the Longest Common Prefix of length L to exist, there must be a common prefix of length L-1 among the array of strings.
4. Hence, Start L from 0 till the length of the first string, and for every L, we will check the Lth character of all the strings.
5. If the Lth character of all the strings is the same, we’ll continue checking for a greater length of the prefix, otherwise, we’re done.

Code

Longest Common Prefix C++ Solution:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int L = 0;
        for(int i=0;i<strs[0].length();i++){
            int ok = 1;
            for(auto& s:strs){
                if(L>=s.length() or s[L]!=strs[0][L]){
                    ok = 0;
                    break;
                }
            }
            if(ok){
                L++;
            }
            else{
                break;
            }
        }
        return strs[0].substr(0,L);
    }
};

Longest Common Prefix Java Solution:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int L = 0;
        for(int i=0;i<strs[0].length();i++){
            int ok = 1;
            for(int j=0;j<strs.length;j++){
                if(L>=strs[j].length() || strs[j].charAt(L)!=strs[0].charAt(L)){
                    ok = 0;
                    break;
                }
            }
            if(ok==1){
                L++;
            }
            else{
                break;
            }
        }
        return strs[0].substring(0,L);
    }
}

Complexity Analysis for Longest Common Prefix Leetcode Solution

Time Complexity

The time complexity of the above code is O(N*L). For every length in range [0, L], we’re checking whether all the strings have the common prefix, where N = the total number of strings and L is the minimum length of the string.

Space Complexity

The space complexity of the above code is O(1) since we’re using the constant space.