CODEWITHSUNDEEP
javascriptarrayssortinglongest-substring
StrugglingCoder
StrugglingCoder

Reputation: 5021

Longest common sub string in a set of strings JavaScript

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"]

Upvotes: 3

Views: 2177

Answers (2)

Sabohat Sobirova
Sabohat Sobirova

Reputation: 1

function commonSubstring(substr, str) {
let awr = '';
let match;
if (str.includes(substr)) return substr;
for (let i = 0; i < substr.length; i++) {
    match = '';
    if (str.includes(substr[i])) {
        match += substr[i];
        if (match.length > awr.length)
            awr = match;
        for (j = 1; i + j < substr.length; j++) {
            if (str.includes(match + substr[i + j])) {
                match += substr[i + j];
                if (match.length > awr.length)
                    awr = match;
                continue;
            }
            else break;
        }
    }
}
return awr;

}

Upvotes: 0

ffxsam
ffxsam

Reputation: 27793

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);
}

Upvotes: 0

Related Questions