I'm solving Leetcode problem: 14 using Javascript

August 29, 2022

I sorted the elements and comparing the first and last string to check the common prefixes. It works for most of the cases, but not for the input ["dog","racecar","car"]. The expected output is "", but what I’m getting is "c" (The "r" in "car" and "r" in "racecar"). I can tell the code to remove the last char, but this will break the other cases such as ["car", "car", "car"]. Not sure what am I missing. Any insights would help me improve.

Thanks

var longestCommonPrefix = function(strs) {
 let count=0
   const sortedString = strs.sort()
   const firstString = sortedString[0]
   const lastString = sortedString[sortedString.length-1]
   for(let i=0; i< firstString.length; i++) {
       if(firstString.charAt(i) === lastString.charAt(i)) {
           count++
       }
   }
    
 console.log(firstString.substring(0, count))
};

longestCommonPrefix(
  ["dog","racecar","car"])

>Solution :

You need to break out of the loop as soon as a match is not found. Otherwise, for example, ra and ca match on the second index, the a – which is undesirable.

var longestCommonPrefix = function(strs) {
  let count = 0
  const sortedString = strs.sort()
  const firstString = sortedString[0]
  const lastString = sortedString[sortedString.length - 1]
  for (let i = 0; i < firstString.length; i++) {
    if (firstString.charAt(i) === lastString.charAt(i)) {
      count++
    } else {
      break;
    }
  }
  console.log(firstString.substring(0, count))
};

longestCommonPrefix(
  ["dog", "racecar", "car"])

or, refactored a bit

const longestCommonPrefix = (strs) => {
  strs.sort();
  const firstString = strs[0];
  const lastString = strs[strs.length - 1];
  let prefixSoFar = '';
  for (let i = 0; i < firstString.length; i++) {
    if (firstString[i] === lastString[i]) {
      prefixSoFar += firstString[i];
    } else {
      return prefixSoFar;
    }
  }
  return prefixSoFar;
};

console.log(longestCommonPrefix(["dog", "racecar", "car"]));