Задача: 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⃣Замените слово найденным корнем и соберите обновленное предложение.
😎 Решение:
fun replaceWords(roots: List<String>, sentence: String): String {
val rootSet = roots.toSet()
fun replace(word: String): String {
for (i in 1..word.length) {
val prefix = word.substring(0, i)
if (rootSet.contains(prefix)) {
return prefix
}
}
return word
}
return sentence.split(" ").joinToString(" ") { replace(it) }
}👉Новости 👉База вопросов