Longest Common Prefix

Given an array of strings , find the longest common prefix among them.

For example,

If you are given the strings “flower”,”flow”,”flight” ,

The longest common prefix among them is “fl”.

Try out the solution here:

https://leetcode.com/problems/longest-common-prefix/

Solution:

You can solve this problem in multiple ways.

We will look into three approaches:

1. Horizontal scanning
2. Vertical scanning
3. Divide and Conqueur

Horizontal Scanning:

In this approach we go from left to right of the array and pick up two words at a time.

We check if the entire first word starts from the beginning of the second word (index 0)

If else we keep stripping off the last letter of the first word.

If at the end nothing remains then there is no common prefix and we return an empty string immediately.

Else we consider the pruned first word as the prefix and pick up the next word in the array and continue the same steps .

Here is the code:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        
        if(strs.length == 1) return strs[0];
     
        

        String prefix= strs[0];
        
        
        for(int i=1;i<strs.length;i++){
            
            
            
            String second = strs[i];
            
            while(strs[i].indexOf(prefix) != 0){
                
                prefix = prefix.substring(0,prefix.length() - 1);
            }
            
            if(prefix.isEmpty()) return "";
            
        }
        
        return prefix;
     
    }
}

In the above code,

If there is only one word in the array we return it.

Else we consider the first word as prefix as explained before and keep pruning it (if entire word doesn’t match with the second word) from the end until it matches the second word in the first iteration.

In the second iteration we compare the pruned prefix with the third word and so on until we reach the end of the array.

The final prefix contains the longest common prefix.

At any stage if any word doesn’t contain any common prefix then we return an empty string immediately.

Time complexity:

Since we scan through each word time complexity is O(m * n) where n is the number of total characters

Space complexity:

We don’t use any extra space , so space complexity is O(1)

Vertical Scanning:

In this approach ,

Instead of scanning from left to right, we take the first word , take one character at a time from the first word and check if all other words contain the same character in the same index position.

We keep tracking the matched letters this way.

Once the letters do not match or we find a shorter matching word we return the string matched so far.

Here is the code:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        
        if(strs.length == 1) return strs[0];
     
        

        for(int i=0;i<strs[0].length();i++){
            
            
            char c = strs[0].charAt(i);
            
            
            for(int j=1;j<strs.length;j++){
                
                
                if( i == strs[j].length() || strs[j].charAt(i) != c){
                    
                    return strs[0].substring(0,i);
                }
            }
            
        }
        
        return strs[0];
    }
}

Time complexity remains the same as before O(n) in the worst case (All the words in the array are the same.)

Space complexity remains the same as well.

Divide and Conquer:

In this approach we divide the given input into half and keep doing it until only two words are left.

We do it on the left half and the right half.

Finally when we get two words (one from the left and one from the right ) ,

We find out the matching characters from these words and find out the prefix.

Similarly we will find out the prefix for every two words .

And then we will find the prefix of the prefixes until we reach the top .

For example if you consider the below input:

“blue”,”black” , “bat”,”bowl”

There are four words.

We will divide them into two first:

“blue”,”black” – left half

“bat”,”bowl” – right half.

We will again divide the left half into two:

“blue” – left

“black” – right

Similarly we will divide the former right half into two:

“bat” – first

“bowl” – second

Now there is only one letter left in each half.

So we will find the matching words from each halves.

Matching prefix between “blue” and “black” is “bl”

Matching prefix between “bat” and “bowl” is “b”.

Now we have two prefixes “bl” and “b”.

We will find the matching prefix between these two now, which is “b”.

So the output is “b”.

Below is the code used to find matching words between two words “left” and “right”:

  int min = Math.min(left.length(),right.length());
        
        
        for(int i=0;i<min;i++){
            
            
            if(left.charAt(i) != right.charAt(i)){
                
                return left.substring(0,i);
            }
        }
        

We take the length of the smaller word and keep moving until we find a matching letter in each word .

Once there is no match we return the matched prefix so far.

Here is the entire code:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        
        if(strs.length == 1) return strs[0];
        
        
        return lcp(0,strs.length - 1,strs);
     
    }
    
    
    
    public String lcp(int l , int r,String[] strs){
        
        //only one word left means return it
        if(l == r) return strs[l];
            
            
            int middle = (l+r)/2;
            
        String left = lcp(l,middle,strs);
        String right = lcp(middle+1,r,strs);
        
        
        int min = Math.min(left.length(),right.length());
        
        
        for(int i=0;i<min;i++){
            
            
            if(left.charAt(i) != right.charAt(i)){
                
                return left.substring(0,i);
            }
        }
        
        return strs[l].substring(0,min);
    }
}

Time complexity:

We traverse through each letter in all the words ,so time complexity is O(n) where n is the total number of characters.

Space complexity:

We make use of O(log m) recursive stack memory (where m is the number of words) since at every iteration we divide the number of words into two and make calls with both the inputs.

And in each recursion stack we also store the prefix. So if we consider the longest prefix length as l , then the total space complexity is O( l * log m)

That’s it!