#ЛитКод
Задача: 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⃣Замените слово найденным корнем и соберите обновленное предложение.

😎 Решение:

function replaceWords($roots, $sentence) {
    $rootSet = array_flip($roots);
    
    $replace = function($word) use ($rootSet) {
        for ($i = 1; $i <= strlen($word); $i++) {
            if (isset($rootSet[substr($word, 0, $i)])) {
                return substr($word, 0, $i);
            }
        }
        return $word;
    };
    
    $words = explode(" ", $sentence);
    $replacedWords = array_map($replace, $words);
    
    return implode(" ", $replacedWords);
}

👉Новости 👉Платформа