Longest Common Prefix

Leave a reply

Table of Contents

Task

 

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:

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

Output:

 "fl"

Example 2:

Input:

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

Output:

 ""

Explanation:

 There is no common prefix among the input strings.

 

Constraints:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lower-case English letters.

This problem was taken from Leetcode Longest Common Prefix

 

Solution

 

Let’s examine this example:

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

the longest common substring is:

 "fl"

Solution 1: Horizontal scanning

We could assume that the whole word could be the common one so we set prefix = ‘flower’
Then we would compare with the rest words and keep removing last character until prefix becomes empty (meaning no common substring was found) or until we have the common substring.

prefix flower flow flight
flower flower flower flower
flowe flowe flowe flowe
flow flow flow flow
flo flo flo flo
fl fl fl fl

 

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    var prefix = strs[0];
    for(var i = 1; i < strs.length; i ++ ) {
        while(strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length - 1);
            if(prefix == "")
                return '';
        }
    }
    return prefix;    
};

 what we just did:
– set up prefix to be the whole 1st word strs[0]
– compare prefix with the second word (strs[1]) and if there is no match, remove the last symbol and keep going until it finds match.

Complexity Analysis

  • Time complexity : O(S) , where S is the sum of all characters in all strings.In the worst case all n strings are the same. The algorithm compares the string S1 with the other strings [S_2 \ldots S_n] There are S character comparisons, where S is the sum of all characters in the input array.
  • Space complexity : O(1). We only used constant extra space.

 

Solution 2: Vertical scanning

Similar but optimized for cases like the one above where we have very short common substring, and we don’t want to scan the whole word.

 

prefix flower flow flight
f f f f
fl fl fl fl
flo flo flo flo

 

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    var prefix;    
    for(var i = 0; i < strs[0].length; i ++ ) {
        var c = strs[0][i];
        for(var j = 0; j < strs.length; j++) {
            if(strs[j][i] != c) {
                return strs[0].substring(0, i);
            }
        }
    }
    return strs[0];    
};

 what we just did:
– Iterate through the words like they are in column.
– compare each character (starting with the first one) between all words. When we find a mismatch, remove the last (mismatched) character and return truncates strs[0]

Leave a Reply