Longest Common Prefix Cont…

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

You can find the complete question here. And if this your first time checking out this question, I would highly recommend you to start with this quick post.

Approach 3:

It was a struggle! I admit it. And I had to look up a few sources. Without a doubt the concept/logic was derived from this brilliant post on GeeksForGeeks. A loud shout-out to its contributors!

The problems in the previous approach(es) —

• Both approaches heavily depended on comparing each characters one-by-one
• Consider a best case scenario where all the strings were exactly the same. But both our solutions would have the worst runtime for this case!

The algorithm that can resolve this problem is our trusty Binary search. Let’s dive into the code without much ado —

//Approach 3:
//Runtime: 3ms
//Memory usage: 32.25MB
class Solution {
    static private char[][] charMatrix;
    public String longestCommonPrefix(String[] strs) {
        if(strs!=null && strs.length>0 && strs[0].length()>0){
            int high = findShortest(strs);
            int low = 0, checkTill = high;
            while(low<high){
                if(matchSubString(strs, checkTill)){
                    low = checkTill;
                } else {
                    high = checkTill;                    
                }
                int checkTillTemp = low + (high-low)/2;
                if(checkTill == checkTillTemp){
                    break;
                }
                checkTill = checkTillTemp;
            }
            return (checkTill>0)?strs[0].substring(0,checkTill):"";
        }
        return "";
    }
    
    private int findShortest(String[] strs){
        int length = Integer.MAX_VALUE;
        for(String s : strs){
            length = Math.min(length, s.length());
        }
        return length;
    }
    
    private boolean matchSubString(String[] strs, int i){
        String sub = strs[0].substring(0,i);
        for(int j = 1; j<strs.length; j++){
            if(!strs[j].substring(0,i).equals(sub)){
                return false;
            }
        }
        return true;
    }
}

Find more posts here.

Cheers & Chao!