Leetcode Longest Common Prefix

Question

I just recently finished the following problem on Leetcode problem. I know it's not the cleanest or fastest solution. I would appreciate if I can get some feedback on how to optimize the code.

The idea is too add all possible prefixes into an array and return the longest possible prefix. I believe this is probably why the algorithm doesn't run as fast as it should.

Also, I would appreciate if someone can assist in determining what the space and time complexity would be for the algorithm below?

var longestCommonPrefix = function(strs) {
const firstWord = strs[0];
const arrResults = [];
let index = 1;
let arrWithoutFirstElement = strs.slice(1, strs.length);
if(strs.length===0)return '';
if(strs.length===1)return strs[0];

while(index <= firstWord.length) {
   if(arrWithoutFirstElement.every(element =>
       element.substring(0,index)===firstWord.substring(0,index))){
       arrResults.push(firstWord.substring(0,index));
   }
   index++;
}

return arrResults.length > 0  ? arrResults[arrResults.length-1] : '';
}

console.log(longestCommonPrefix(["flower","flow","flight"]));

Community · Accepted Answer · 2020-06-10 13:24:26Z

Fast strings in Javascript

It is important to note that something as simple as assigning a string to a variable will cost the length of the string in complexity a = "12345" will cost 5 characters. Assign to another variable and the cost is the same b = a will cost 5.

Every time you assign a string you need to count the length of that string. If you copy an array of strings then you move all the characters, not just the number of strings in the array.

You do a lot of string assignments in your code.

Avoid string assignment

The trick to handling strings is to avoid assigning strings if you can. Arrays and string array character referencing (eg a = "abcdef"; b = a[1]) lets you treat the JS string like a C (char *) string. You dont copy the string, you are just indexing into the string.

The only time any sequence of characters are copied is on the return. The performance increase is very significant.

const longestCommonPrefix = words => {
    var i, pos = 0, len = words.length;
    const char = words[0][pos];
    var min = words[0].length;
    for (i = 1; i < len; i++) { // finds the min word length and check first char
        min = words[i].length < min ? words[i].length : min;
        if (char !== words[i][pos] || pos === min) { return "" }
    }    
    pos ++;
    while (pos < min) {  // check up to min word length.
        const char = words[0][pos];
        for (i = 1; i <len; i++) {
            if (char !== words[i][pos]) { return words[0].substring(0,pos) }
        }
        pos ++;
    }
    return words[0].substring(0,pos);
}

Stack Exchange Network

Leetcode Longest Common Prefix

1 Answer 1

Fast strings in Javascript

Avoid string assignment

You must log in to answer this question.

Hot Network Questions

Leetcode Longest Common Prefix

1 Answer 1

Fast strings in Javascript

Avoid string assignment

You must log in to answer this question.

Related

Hot Network Questions