Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

Approach1: Vertical Scanning

This approach consists of iterating over the characters of an arbitrarily chosen String from the array (in this example, we use the string at index 0) and verify by looping on each of the Strings of the array if they contain that same character at the position specified by the initially chosen String (Outer Loop).

• Iterate over first String of given array (in lieu of a traditionnal loop or a for-each loop, we use enumerate to simultaneously get the position of the pointer as well as the character it is pointing to.)

• We loop over the Strings of the array and check whether they have the same character at position i then strs[0].

• We stop the loop for the below conditions:

  • If i equals or surpasses the length of a given word meaning that there cannot be a longer common prefix, we then return the substring.

  • If the chracters are different at position i , we return the substring[0:i] indicating that it is the longest prefix shared by all the strings constituting the array.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        
        for i, ch in enumerate(strs[0]):
            for word in strs:
                if i >= len(word) or word[i] != ch:
                    return word[:i]
        return strs[0]

Time: O(mn) m = Length of longest String n = length of array strs. Space: O(1)

Java Version of Vertical Scanning

class Solution {
    //Vertical Scanning
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0) return "";
        StringBuilder sb = new StringBuilder();
        
        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 sb.toString();
                }
            }
            sb.append(c);
        }
        return sb.toString();
    }
}

Approach2: Horizontal Scanning

The code for this approach as well as it's underlying concept is relatively easier to grasp than the above.

• We again select the first String (strs[0]) and reference it to a string holder called pre.

• We then loop over each subsequent Strings in the array and check whether or not they start with pre.

• If the String does not start with pre, we subseqently reduce it by one index from the right by getting it's substring. We use the while loop as we want to ensure that for each iteration, pre is being reduced until it is a prefix.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        
        pre = strs[0]
        
        for i in range(1, len(strs)):
            while not strs[i].startswith(pre):
                pre = pre[:-1]
        return pre

O(n m (m + m)), which is O(n m 2m), which is O(n * m^2) Because for n strings it does m times startswith (which is O(m)) and m times substring (which is O(m)).

Java Version of Vertical Scanning

class Solution {
    //Horizontal Scanning
     if(strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        for(int i = 0; i < strs.length; i++){
            while(strs[i].indexOf(prefix) != 0){
                prefix = prefix.substring(0, prefix.length() - 1);
                if(prefix.length() == 0) return "";
            }
        }
        return prefix;
    }
}