Задача: 648. Replace Words
В английском языке есть понятие "корень", за которым может следовать какое-то другое слово, чтобы образовать другое более длинное слово - назовем это слово производным. Например, если за корнем "help" следует слово "ful", мы можем образовать производное "helpful". Дайте словарь, состоящий из множества корней, и предложение, состоящее из слов, разделенных пробелами, замените все производные в предложении на образующий их корень. Если производное может быть заменено более чем одним корнем, замените его корнем, имеющим наименьшую длину. Верните предложение после замены.
Пример:
Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
👨💻 Алгоритм:
1⃣Преобразуйте словарь корней в набор для быстрого поиска.
2⃣Пройдите по каждому слову в предложении и найдите самый короткий корень, который является префиксом этого слова.
3⃣Замените слово найденным корнем и соберите обновленное предложение.
😎 Решение:
var replaceWords = function(roots, sentence) {
const rootSet = new Set(roots);
const replace = (word) => {
for (let i = 1; i <= word.length; i++) {
if (rootSet.has(word.slice(0, i))) {
return word.slice(0, i);
}
}
return word;
};
return sentence.split(' ').map(replace).join(' ');
};👉Новости 👉База вопросов