SeniorКодИногдаЕщё не отвечали
Удалить смайлики :-))) и :-((( из сообщения за один проход
Удалите из сообщения каждый смайлик по шаблону :-)+ или :-(+ за линейное время, без регулярных выражений. Вложенные смайлики НЕ обрабатывайте особо: :-:-)))((( даёт :-(((, а не пустую строку.
Требования:
- Один проход, O(n); O(1) доп. при изменении на месте.
std::string removeSmileys(const std::string& s) {
// ваш код здесь
}Допишите реализацию.
Один проход как небольшой автомат. На каждой позиции проверяйте :, затем -, затем серию ) или (; если найдено, пропустите весь токен и продолжите за ним, иначе скопируйте символ в вывод. Без отката в выведенный текст, поэтому вложенность не схлопывается. O(n).
- ✗Откатываться и схлопывать вложенные смайлики, которые спецификация велит не трогать
- ✗Забыть, что смайлику нужны двоеточие, дефис И непустая серия скобок
- ✗Делать повторные проходы стирания, превращая задачу одного прохода в O(n²)
- →Почему отказ от отката даёт поведение без вложенности, как требует спецификация?
- →Как сделать это по-настоящему на месте с индексом записи?
Оглавление
Задача
Удалите смайлики :-)+ и :-(+ за один проход, без регулярных выражений и без схлопывания вложенности.
Решение
#include <string>
std::string removeSmileys(const std::string& s) {
std::string out;
size_t i = 0, n = s.size();
while (i < n) {
if (i + 2 < n && s[i] == ':' && s[i+1] == '-' &&
(s[i+2] == ')' || s[i+2] == '(')) {
char br = s[i+2];
size_t j = i + 2;
while (j < n && s[j] == br) ++j; // серия скобок
i = j; // пропустить весь смайлик
} else {
out.push_back(s[i++]); // обычный символ
}
}
return out;
}Ключевые моменты
- Автомат:
:→-→ серия)или(, иначе обычный символ. - Не откатываемся в вывод — поэтому вложенность не схлопывается.
- Один проход, O(n).
Оглавление
