[tabby title=”Task”]

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

 "fl"

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

 ""

 There is no common prefix among the input strings.

This problem was taken from Leetcode Longest Common Prefix

[tabby title=”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.

/**
 * @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][S2​…Sn​] 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.

/**
 * @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]

[tabbyending]