Сложность: easy
Даны две строки s и t. Верните true, если s является подпоследовательностью t, иначе верните false.
Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (возможно, ни одного) символов без нарушения относительных позиций оставшихся символов. (например, "ace" является подпоследовательностью "abcde", тогда как "aec" не является).
Пример:
Input: s = "abc", t = "ahbgdc"
Output: true
👨💻 Алгоритм:
1⃣Назначьте два указателя: левый для исходной строки и правый для целевой строки. Эти указатели будут использоваться для итерации по строкам и сравнения их символов.
2⃣Перемещайте указатели в зависимости от совпадения символов. Если символы на текущих позициях указателей совпадают, переместите оба указателя на один шаг вперед. Если символы не совпадают, переместите только правый указатель целевой строки.
3⃣Итерация завершается, когда один из указателей выходит за пределы своей строки. Если в конце итерации все символы исходной строки были найдены в целевой строке, исходная строка является подпоследовательностью целевой строки.
😎 Решение:
class Solution {
public boolean isSubsequence(String s, String t) {
int leftBound = s.length(), rightBound = t.length();
int pLeft = 0, pRight = 0;
while (pLeft < leftBound && pRight < rightBound) {
if (s.charAt(pLeft) == t.charAt(pRight)) {
pLeft += 1;
}
pRight += 1;
}
return pLeft == leftBound;
}
}Ставь 👍 и забирай 📚 Базу знаний