Текстовый редактор подчёркивает слова, которых он не знает. Загрузите словарь в множество (хеш-таблицу), чтобы каждый поиск был быстрым, а затем просмотрите текст.
Слово - это максимальная последовательность английских букв (A-Z, a-z) и апострофов; любой другой символ (пробелы, цифры, знаки препинания) разделяет слова. Слова сравниваются без учёта регистра, поэтому The совпадает со словарной записью the.
Реализуйте spell_checker(dictionary, text).
Входные данные
dictionary: известные слова. Они могут быть записаны в любом регистре.
text: текст для проверки.
Выходные данные
Верните слова с ошибками строчными буквами в порядке их первого появления в тексте, каждое по одному разу. Если все слова известны, верните пустой список.
Ограничения
0 ≤ размер словаря ≤ 2000
0 ≤ длина text ≤ 10 000
Примеры
Ввод:
dictionary = ["the", "cat", "sat", "on", "mat"]
text = "The cat sat on teh mat, the cta!"
Ожидаемый вывод:
expected = ["teh", "cta"]
Ввод:
std::vector<std::string> dictionary = {"the", "cat", "sat", "on", "mat"};
std::string text = "The cat sat on teh mat, the cta!";
Ожидаемый вывод:
std::vector<std::string> expected = {"teh", "cta"};
Ввод:
string[] dictionary = new string[] {"the", "cat", "sat", "on", "mat"};
string text = "The cat sat on teh mat, the cta!";
Ожидаемый вывод:
string[] expected = new string[] {"teh", "cta"};
Пояснение
teh и cta нет в словаре. Для остальных слов регистр и запятая не важны: ["teh", "cta"].
Ввод:
dictionary = ["Don't", "stop"]
text = "don't STOP, dont stop dont"
Ожидаемый вывод:
expected = ["dont"]
Ввод:
std::vector<std::string> dictionary = {"Don't", "stop"};
std::string text = "don't STOP, dont stop dont";
Ожидаемый вывод:
std::vector<std::string> expected = {"dont"};
Ввод:
string[] dictionary = new string[] {"Don't", "stop"};
string text = "don't STOP, dont stop dont";
Ожидаемый вывод:
string[] expected = new string[] {"dont"};
Пояснение
don't сохраняет апостроф и находится в словаре; dont неизвестно и выводится один раз: ["dont"].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Приведите словарные слова к нижнему регистру один раз, когда строите множество.
Подсказка 2
Собирайте текущее слово посимвольно и завершайте его, когда встретите символ, который не является ни буквой, ни апострофом.
Подсказка 3
Храните второе множество для уже выведенных слов.
Ожидаемая сложность
время O(D + T), доп. память O(D + T)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.