Сложность: 🟢 Легкая
ℹ️ Описание
Дано две строки s и t. Напишите функцию, которая возвращает true, если s является подпоследовательностью t, или false в противном случае.
Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (может быть ни одного) символов без нарушения относительного положения остальных символов. (т. е. «ace» является подпоследовательностью abcde, а «aec» — нет).
⚠️ Ограничения
— Длина строки s находится в диапазоне от 0 до 100
— Длина строки t находится в диапазоне от 0 до 10000
— В строках могут присутствовать только латинские буквы в нижнем регистре
1️⃣ Пример
Входные данные
s = "abc"
t = "ahbgdc"
Ответ
true
2️⃣ Пример
Входные данные
s = "axc"
t = "ahbgdc"
Ответ
false
✅ Решение
Для решения задачи воспользуемся самым простым способом, а именно движением по обеим строкам с помощью двух указателей.
Мы запускаем цикл по всем символам строки t и сравниваем их с символами строки s. Для отслеживания позиции в строке s мы будем использовать указатель pos.
- Если символы совпадают, мы двигаем указатель строки pos на одну позицию вперед.
- Если после прохода по всем символам строки t указатель pos указывает на конец строки s, значит строка s является подпоследовательностью строки t.
- Если во время очередной итерации выполняется это же условие, то мы моем досрочно завершить выполнение функции и вернуть true, так как дальнейший проход по строке t не имеет смысла.
Посмотреть реализацию в блоге
#strings #easy