Longest Common Prefix

Problem

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:

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

My Solution

const longestCommonPrefix = (strs) => {
let result = "";
let single = [];
let match = [];
let i = 0;
while (single.length === match.length) {
single = strs.map((str) => str[i]);
match = single.filter((ltr) => ltr === single[i]);
single.length === match.length && (result += match[0]);
i++;
}
return result;
};

This is my first solution! Logic is to start with getting the single letter array and the matching array. Then, if match.length is equal to single.length, which is the same as strs.length, it added to result array. And this goes until the single array length equal to the match array length.

This works fine, however, the problem is over the memory limitations. I got runtime error by this solution. I tried to approach it in a different way.

const longestCommonPrefix = (strs) => {
if (strs.length === 0) return "";
let prefix = strs[0];
for (let i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) !== 0) {
prefix = prefix.substring(0, prefix.length - 1);
}
}
return prefix;
};

This is my second solution, it simply defines the first letter is as prefix. then it subtracts the letter from the end until remaining only the common letter.

This works well! simpler and better I guess!

This time, there is no best practice in the Leetcode community. Done!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store