Leetcode problem 3 - Longest Common Prefix

Longest Common Prefix

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.

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

First of all, I should sort our strs array to rearrange alphabetical order. I’m going to compare first and last element after sorting the array. Let say, there is the array is [“flower”, “dog”, “flow”]. As I said, first and last element will be compared, so the output will be “fl” which is wrong answer, so sorting should be first task.

In for loop, I used “if statement” to check if the first element and last element are same. If they are different value, first element will be cut off by substring method as much as “i”.

Let’s take a look at first test case.

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

After sorting the array

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

First element is “flight”.

if (strs[0][i] !== strs[strs.length - 1][i]) {

strs[0][i] indicates “f” in “flight” element. strs[strs.length - 1][i] indicates “f” in “flower” element. If they are different value, return the first element cut off by substring method as much as “i”.

return strs[0].substring(0, i);

So, first interation will be passed, and second is as well.

When third interation, the result will be returned because third word in “flight” which is “i” is not same with third word in “flower” which is “o”

return strs[0];

Then, the result is “fl”