Задача: 648. Replace Words
Сложность: medium

В английском языке есть понятие "корень", за которым может следовать какое-то другое слово, чтобы образовать другое более длинное слово - назовем это слово производным. Например, если за корнем "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⃣Замените слово найденным корнем и соберите обновленное предложение.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public string ReplaceWords(IList<string> roots, string sentence) {
        var rootSet = new HashSet<string>(roots);
        
        string Replace(string word) {
            for (int i = 1; i <= word.Length; i++) {
                string prefix = word.Substring(0, i);
                if (rootSet.Contains(prefix)) {
                    return prefix;
                }
            }
            return word;
        }
        
        return string.Join(" ", sentence.Split(' ').Select(Replace));
    }
}

Ставь 👍 и забирай 📚 Базу знаний