Longest common prefix

up vote
3
down vote

favorite

I have made a function for finding the longest common prefix for the challenge on the leetcode site. This is the code:

var longestCommonPrefix = function(strs) {

    let longestPrefix = '';

    if (strs.length > 0) {

      longestPrefix = strs[0];

      for (let i = 1; i < strs.length; i++) {

        for (let j = 0; j < longestPrefix.length; j++) {

          if (strs[i][j] != longestPrefix[j]) {

            longestPrefix = longestPrefix.slice(0, j);

            break;

          }

        }

      }

    }



    return longestPrefix;

};

I am sure there is a way to make this code better, but not sure how to do that. Would appreciate any help.

edited 40 mins ago

asked Dec 7 '17 at 13:59

Leff

1747

add a comment |

up vote
3
down vote

favorite

I have made a function for finding the longest common prefix for the challenge on the leetcode site. This is the code:

var longestCommonPrefix = function(strs) {

    let longestPrefix = '';

    if (strs.length > 0) {

      longestPrefix = strs[0];

      for (let i = 1; i < strs.length; i++) {

        for (let j = 0; j < longestPrefix.length; j++) {

          if (strs[i][j] != longestPrefix[j]) {

            longestPrefix = longestPrefix.slice(0, j);

            break;

          }

        }

      }

    }



    return longestPrefix;

};

I am sure there is a way to make this code better, but not sure how to do that. Would appreciate any help.

edited 40 mins ago

asked Dec 7 '17 at 13:59

Leff

1747

add a comment |

up vote
3
down vote

favorite

I have made a function for finding the longest common prefix for the challenge on the leetcode site. This is the code:

var longestCommonPrefix = function(strs) {

    let longestPrefix = '';

    if (strs.length > 0) {

      longestPrefix = strs[0];

      for (let i = 1; i < strs.length; i++) {

        for (let j = 0; j < longestPrefix.length; j++) {

          if (strs[i][j] != longestPrefix[j]) {

            longestPrefix = longestPrefix.slice(0, j);

            break;

          }

        }

      }

    }



    return longestPrefix;

};

I am sure there is a way to make this code better, but not sure how to do that. Would appreciate any help.

edited 40 mins ago

asked Dec 7 '17 at 13:59

Leff

1747

I have made a function for finding the longest common prefix for the challenge on the leetcode site. This is the code:

var longestCommonPrefix = function(strs) {

    let longestPrefix = '';

    if (strs.length > 0) {

      longestPrefix = strs[0];

      for (let i = 1; i < strs.length; i++) {

        for (let j = 0; j < longestPrefix.length; j++) {

          if (strs[i][j] != longestPrefix[j]) {

            longestPrefix = longestPrefix.slice(0, j);

            break;

          }

        }

      }

    }



    return longestPrefix;

};

I am sure there is a way to make this code better, but not sure how to do that. Would appreciate any help.

javascript algorithm strings programming-challenge

edited 40 mins ago

asked Dec 7 '17 at 13:59

Leff

1747

edited 40 mins ago

asked Dec 7 '17 at 13:59

Leff

1747

edited 40 mins ago

asked Dec 7 '17 at 13:59

Leff

1747

asked Dec 7 '17 at 13:59

Leff

1747

asked Dec 7 '17 at 13:59

Leff

1747

add a comment |

2 Answers
2

active

oldest

votes

up vote
2
down vote

From a short review;

You should sort the strings by length ascending if you start by assigning longestPrefix = strs[0]; the prefix cannot be longer than the shortest string.

I would assign longestPrefix[j] to a variable, avoiding an array access in a nested loop

I would return the found value instead of calling break
- Break only exits one iteration in the loop anyway
- It seems okay that if no string list is provided, that undefined is returned

Personal preference, I prefer list over strs

function(strs) creates an anonymous function, which is terrible in stack traces, just use the good old function longestCommonPrefix(strs) {

edited Dec 7 '17 at 17:36

answered Dec 7 '17 at 15:59

konijn

26.9k453235

add a comment |

up vote
2
down vote

I would find the alphabetically smallest and largest string and just run your algorithm on these two. That would avoid the embedded loop.

var longestCommonPrefix = function(strs) {

    if (!strs)

        return '';



    let smallest = strs.reduce( (min, str) => min < str ? min : str, strs[0] );

    let largest  = strs.reduce( (min, str) => min > str ? min : str, strs[0] );



    for (let i=0; i<smallest.length; i++) {

        if (smallest[i] != largest[i])

            return smallest.substr(0,i);

    }



    return '';

};

In answer to konijn it would be minimally faster to get the smallest/largest by doing:

let smallest = strs[0];

let largest  = strs[0];

for (let i=1; i<strs.length; i++) {

  let s= strs[i];

  if (s > largest)  largest = s;

  if (s < smallest) smallest = s;

}

edited Dec 7 '17 at 22:37

answered Dec 7 '17 at 17:42

Marc Rohloff

2,99736

Would a sort with a pop and an unshift not be faster?
– konijn
Dec 7 '17 at 18:40

1

fwiw, I wouldn't use shift since it requires moving all the elements in the array, [0] would be quicker. Even pop requires modifying the array, but to answer your comment most sorts are quite expensive O(n.log n) or O(n^2) and require a lot of moving and copying. The two calculations could be combined in a loop if performance was really critical (see my addition)
– Marc Rohloff
Dec 7 '17 at 22:34

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f182217%2flongest-common-prefix%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

up vote
2
down vote

From a short review;

You should sort the strings by length ascending if you start by assigning longestPrefix = strs[0]; the prefix cannot be longer than the shortest string.

I would assign longestPrefix[j] to a variable, avoiding an array access in a nested loop

I would return the found value instead of calling break
- Break only exits one iteration in the loop anyway
- It seems okay that if no string list is provided, that undefined is returned

Personal preference, I prefer list over strs

function(strs) creates an anonymous function, which is terrible in stack traces, just use the good old function longestCommonPrefix(strs) {

edited Dec 7 '17 at 17:36

answered Dec 7 '17 at 15:59

konijn

26.9k453235

add a comment |

up vote
2
down vote

From a short review;

You should sort the strings by length ascending if you start by assigning longestPrefix = strs[0]; the prefix cannot be longer than the shortest string.

I would assign longestPrefix[j] to a variable, avoiding an array access in a nested loop

I would return the found value instead of calling break
- Break only exits one iteration in the loop anyway
- It seems okay that if no string list is provided, that undefined is returned

Personal preference, I prefer list over strs

function(strs) creates an anonymous function, which is terrible in stack traces, just use the good old function longestCommonPrefix(strs) {

edited Dec 7 '17 at 17:36

answered Dec 7 '17 at 15:59

konijn

26.9k453235

add a comment |

up vote
2
down vote

From a short review;

You should sort the strings by length ascending if you start by assigning longestPrefix = strs[0]; the prefix cannot be longer than the shortest string.

I would assign longestPrefix[j] to a variable, avoiding an array access in a nested loop

I would return the found value instead of calling break
- Break only exits one iteration in the loop anyway
- It seems okay that if no string list is provided, that undefined is returned

Personal preference, I prefer list over strs

function(strs) creates an anonymous function, which is terrible in stack traces, just use the good old function longestCommonPrefix(strs) {

edited Dec 7 '17 at 17:36

answered Dec 7 '17 at 15:59

konijn

26.9k453235

From a short review;

You should sort the strings by length ascending if you start by assigning longestPrefix = strs[0]; the prefix cannot be longer than the shortest string.

I would assign longestPrefix[j] to a variable, avoiding an array access in a nested loop

I would return the found value instead of calling break
- Break only exits one iteration in the loop anyway
- It seems okay that if no string list is provided, that undefined is returned

Personal preference, I prefer list over strs

function(strs) creates an anonymous function, which is terrible in stack traces, just use the good old function longestCommonPrefix(strs) {

edited Dec 7 '17 at 17:36

answered Dec 7 '17 at 15:59

konijn

26.9k453235

edited Dec 7 '17 at 17:36

answered Dec 7 '17 at 15:59

konijn

26.9k453235

answered Dec 7 '17 at 15:59

konijn

26.9k453235

answered Dec 7 '17 at 15:59

konijn

26.9k453235

add a comment |

up vote
2
down vote

I would find the alphabetically smallest and largest string and just run your algorithm on these two. That would avoid the embedded loop.

var longestCommonPrefix = function(strs) {

    if (!strs)

        return '';



    let smallest = strs.reduce( (min, str) => min < str ? min : str, strs[0] );

    let largest  = strs.reduce( (min, str) => min > str ? min : str, strs[0] );



    for (let i=0; i<smallest.length; i++) {

        if (smallest[i] != largest[i])

            return smallest.substr(0,i);

    }



    return '';

};

In answer to konijn it would be minimally faster to get the smallest/largest by doing:

let smallest = strs[0];

let largest  = strs[0];

for (let i=1; i<strs.length; i++) {

  let s= strs[i];

  if (s > largest)  largest = s;

  if (s < smallest) smallest = s;

}

edited Dec 7 '17 at 22:37

answered Dec 7 '17 at 17:42

Marc Rohloff

2,99736

Would a sort with a pop and an unshift not be faster?
– konijn
Dec 7 '17 at 18:40

1

fwiw, I wouldn't use shift since it requires moving all the elements in the array, [0] would be quicker. Even pop requires modifying the array, but to answer your comment most sorts are quite expensive O(n.log n) or O(n^2) and require a lot of moving and copying. The two calculations could be combined in a loop if performance was really critical (see my addition)
– Marc Rohloff
Dec 7 '17 at 22:34

add a comment |

up vote
2
down vote

I would find the alphabetically smallest and largest string and just run your algorithm on these two. That would avoid the embedded loop.

var longestCommonPrefix = function(strs) {

    if (!strs)

        return '';



    let smallest = strs.reduce( (min, str) => min < str ? min : str, strs[0] );

    let largest  = strs.reduce( (min, str) => min > str ? min : str, strs[0] );



    for (let i=0; i<smallest.length; i++) {

        if (smallest[i] != largest[i])

            return smallest.substr(0,i);

    }



    return '';

};

In answer to konijn it would be minimally faster to get the smallest/largest by doing:

let smallest = strs[0];

let largest  = strs[0];

for (let i=1; i<strs.length; i++) {

  let s= strs[i];

  if (s > largest)  largest = s;

  if (s < smallest) smallest = s;

}

edited Dec 7 '17 at 22:37

answered Dec 7 '17 at 17:42

Marc Rohloff

2,99736

Would a sort with a pop and an unshift not be faster?
– konijn
Dec 7 '17 at 18:40

1

fwiw, I wouldn't use shift since it requires moving all the elements in the array, [0] would be quicker. Even pop requires modifying the array, but to answer your comment most sorts are quite expensive O(n.log n) or O(n^2) and require a lot of moving and copying. The two calculations could be combined in a loop if performance was really critical (see my addition)
– Marc Rohloff
Dec 7 '17 at 22:34

add a comment |

up vote
2
down vote

I would find the alphabetically smallest and largest string and just run your algorithm on these two. That would avoid the embedded loop.

var longestCommonPrefix = function(strs) {

    if (!strs)

        return '';



    let smallest = strs.reduce( (min, str) => min < str ? min : str, strs[0] );

    let largest  = strs.reduce( (min, str) => min > str ? min : str, strs[0] );



    for (let i=0; i<smallest.length; i++) {

        if (smallest[i] != largest[i])

            return smallest.substr(0,i);

    }



    return '';

};

In answer to konijn it would be minimally faster to get the smallest/largest by doing:

let smallest = strs[0];

let largest  = strs[0];

for (let i=1; i<strs.length; i++) {

  let s= strs[i];

  if (s > largest)  largest = s;

  if (s < smallest) smallest = s;

}

edited Dec 7 '17 at 22:37

answered Dec 7 '17 at 17:42

Marc Rohloff

2,99736

I would find the alphabetically smallest and largest string and just run your algorithm on these two. That would avoid the embedded loop.

var longestCommonPrefix = function(strs) {

    if (!strs)

        return '';



    let smallest = strs.reduce( (min, str) => min < str ? min : str, strs[0] );

    let largest  = strs.reduce( (min, str) => min > str ? min : str, strs[0] );



    for (let i=0; i<smallest.length; i++) {

        if (smallest[i] != largest[i])

            return smallest.substr(0,i);

    }



    return '';

};

In answer to konijn it would be minimally faster to get the smallest/largest by doing:

let smallest = strs[0];

let largest  = strs[0];

for (let i=1; i<strs.length; i++) {

  let s= strs[i];

  if (s > largest)  largest = s;

  if (s < smallest) smallest = s;

}

edited Dec 7 '17 at 22:37

answered Dec 7 '17 at 17:42

Marc Rohloff

2,99736

edited Dec 7 '17 at 22:37

answered Dec 7 '17 at 17:42

Marc Rohloff

2,99736

answered Dec 7 '17 at 17:42

Marc Rohloff

2,99736

answered Dec 7 '17 at 17:42

Marc Rohloff

2,99736

Would a sort with a pop and an unshift not be faster?
– konijn
Dec 7 '17 at 18:40

1

fwiw, I wouldn't use shift since it requires moving all the elements in the array, [0] would be quicker. Even pop requires modifying the array, but to answer your comment most sorts are quite expensive O(n.log n) or O(n^2) and require a lot of moving and copying. The two calculations could be combined in a loop if performance was really critical (see my addition)
– Marc Rohloff
Dec 7 '17 at 22:34

add a comment |

Would a sort with a pop and an unshift not be faster?
– konijn
Dec 7 '17 at 18:40

1

fwiw, I wouldn't use shift since it requires moving all the elements in the array, [0] would be quicker. Even pop requires modifying the array, but to answer your comment most sorts are quite expensive O(n.log n) or O(n^2) and require a lot of moving and copying. The two calculations could be combined in a loop if performance was really critical (see my addition)
– Marc Rohloff
Dec 7 '17 at 22:34

Would a sort with a pop and an unshift not be faster?
– konijn
Dec 7 '17 at 18:40

fwiw, I wouldn't use shift since it requires moving all the elements in the array, [0] would be quicker. Even pop requires modifying the array, but to answer your comment most sorts are quite expensive O(n.log n) or O(n^2) and require a lot of moving and copying. The two calculations could be combined in a loop if performance was really critical (see my addition)
– Marc Rohloff
Dec 7 '17 at 22:34

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Code Review Stack Exchange!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Krdytkyu