Longest Common Prefix

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

Example 1:

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

Example 2:

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

You may view the full question here.

Solutions:

//Approach 1:
//Runtime: 4ms
//Memory usage: 37.9MB
class Solution {
    public String longestCommonPrefix(String[] strs) {
        int lastIndex;
        if(strs!=null && strs.length>0){
            lastIndex = (strs[0]).length();
        
            char[] curr = strs[0].toCharArray();
            char[] next;
            for(int i = 1; i<strs.length; i++){
                next = strs[i].toCharArray();
                lastIndex = commonPrefix(curr, next, lastIndex);
                curr = next;
            }
            if(lastIndex>0){
                return strs[0].substring(0, lastIndex);
            }
        }
        return "";
    }
    
    private int commonPrefix(char[] arrayA, char[] arrayB, int checkTill){
        int i = 0;
        checkTill = Math.min(Math.min(checkTill, arrayA.length), arrayB.length);
        for(; i<checkTill; i++){
            if(arrayA[i]!=arrayB[i]){
                break;
            }
        }
        return i;
    }
}
//**************************************************************//
//Approach 2:
//Runtime: 4ms
//Memory usage: 37.9MB
class Solution {
    static private String[] strsG;
    public String longestCommonPrefix(String[] strs) {
        int lastIndex;
        this.strsG = strs;
        if(strsG!=null && strsG.length>0){
            lastIndex = (strsG[0]).length();
            int i = 0;
            for(; i<lastIndex; i++){
                if(!commonPrefix(i)){
                    break;
                }
            }
            return strsG[0].substring(0,i);
        }
        return "";
    }
    
    private boolean commonPrefix(int checkAt){
        char ref;
        if(strsG[0].length()>checkAt){
            ref = strsG[0].charAt(checkAt);
            for(int i = 1; i<strsG.length; i++){
                if(strsG[i].length()>checkAt && ref==strsG[i].charAt(checkAt)){
                    continue;
                } else {
                    return false;
                }
            }
            return true;
        } else {
            return false;
        }
    }
}

The first approach simply uses the plain logic of comparing the strings two at a time to find the longest common prefix, and then iterate through the list of strings.

The second approach uses the principle that the prefix needs to be common across all the strings in the list. Therefore, the characters in each index position are compared index-wise for each of the strings in the list.

Check out this post for a faster solution.

Find more posts here.

Cheers & Chao!