Longest common sub string in a set of strings JavaScript

user_3655102 0
Viewed 1540

I was trying to find longest common substring in a set of strings in JavaScript.

I got the idea from Find the longest common starting substring in a set of strings

but I am not only looking for staring sub string

So, I went ahead with following:

I guess it works as expected but there is an overhead of map and sort.

function longestCommonSubstring(array) {
    // Copy the array
    let arr = array.slice().sort();
    // For each individual string sort them 
    arr = arr.map(a => a.split('').sort().join(''));
    // Check the first and last string and check till chars match
    let a0 = arr[0],
        aLast = arr[arr.length -1],
        len = arr[0].length,
        i = 0;
    while(i < len && a0[i] === aLast[i]) i++;
    // return
    return a0.substring(0,i);
}

Am I doing any wrong? Can it be done in much more efficient way ?

INPUT ["abc","cxabgi"]

OUTPUT ["ab"]

longest-substring sorting arrays javascript
1 Answers
function longestCommonSubstring(array) {
  const sortedArray = [...array].sort();
  const firstItem = sortedArray[0];
  const lastItem = sortedArray[sortedArray.length - 1];
  const firstItemLength = firstItem.length;
  let i = 0;

  while (i < firstItemLength && firstItem.charAt(i) === lastItem.charAt(i)) {
    i++;
  }

  return firstItem.substring(0, i);
}
user_52288060
Related