Есть задача - нахождение общего префикса у каждого слова
пример: Input: strs = [“flower”,“flow”,“flight”] Output: “fl”
Я решил ее так (см ниже) но есть же решенее короче и лаконичнее это точно. Вот прошу предложить варианты.
var longestCommonPrefix = function(strs) {
if (strs.length < 1) {
return "";
} else if (strs.length === 1) {
return strs[0];
}
let firstWord = strs[0];
while (strs.length > 1) {
const secondWord = strs.splice(strs.length -1);
const separateByLetterSecondWord = secondWord[0].split("");
const separateByLetterFirstWord = firstWord.split("");
const commonLetters = [];
// firstWord = separateByLetterFirstWord.filter((letter, i) => letter === separateByLetterSecondWord[i]).join("");
for (i = 0; i < separateByLetterFirstWord.length; i += 1) {
if (separateByLetterFirstWord[i] !== separateByLetterSecondWord[i]) {
break;
} else if (separateByLetterFirstWord[i] === separateByLetterSecondWord[i]) {
commonLetters.push(separateByLetterFirstWord[i])
}
}
firstWord = commonLetters.join("");
}
return firstWord;
}
console.log(longestCommonPrefix(["flower","flight","flow"]));
function getLongestPrefix(words) {
if (words.length === 0) {
return ''
}
const firstWord = words[0]
let prefix = ''
for (let i = 0; i < firstWord.length; i += 1) {
prefix = firstWord.slice(0, i + 1) // can never be longer than the word itself
const isCommonPrefix = words.every((word) => {
return word.indexOf(prefix) === 0
})
if (!isCommonPrefix) {
// previous prefix was the longest common prefix
prefix = prefix.slice(0, prefix.length - 1)
break
}
}
return prefix
}
console.log(getLongestPrefix(["flower","flight","flow"])) // fl
console.log(getLongestPrefix(["flower","floight","flow"])) // flo
console.log(getLongestPrefix(["flower"])) // flower
console.log(getLongestPrefix([])) // ''
Тут несколько хитростей. Так как общий префикс не может быть длинее чем любое слово, то алгоритмически можно брать часть первого слова, смотреть начинаются ли все слова в массиве с этой части первого слова, и если во всех словах эта часть входит в начало слова, то брать следующую, большую часть первого слова и снова пробегаться по всем словам массива. Плюс добавить обработку граничных случаев когда массив пуст. Не самое оптимальное, зато достаточно простое решение (когда знаешь историю в словах что именно реализуется).
const s = ['flower', 'flow', 'flight'],
a = ['sunday', 'sunny', 'sun'],
z = ['sunday', 'sunny', 'sun', 'cunning'];
function pref(arr){
if(!Array.isArray(arr) || !arr.length) return 'Wrong data passed';
const ar = arr.sort( (a, b) => a.length - b.length );
let found = '';
for(let n of ar[0]){
if(ar.every( x => x.at(ar[0].indexOf(n)) == n )){ found += n; }
else{ break; }
}
return found.length ? found : 'No common prefix found';
}
console.log( pref(s) ); // fl
console.log( pref(a) ); // sun
console.log( pref(z) ); // No common prefix found
console.log( pref([]) ); // Wrong data passed
console.log( pref('shit') ); // Wrong data passed