392. Is Subsequence

LeetCode задача 392

Задача

Даны две строки s и t. Верните true, если s является подпоследовательностью t, или false в противном случае.

Подпоследовательность строки - это новая строка, которая формируется из исходной строки путем удаления некоторых (может быть ни одного) символов без нарушения относительных позиций оставшихся символов. (например, “ace” является подпоследовательностью “abcde”, в то время как “aec” - нет).

Подсказки

Следуя за обеими строками одновременно с помощью двух указателей, вы можете определить, является ли одна строка подпоследовательностью другой.

Подход

Мы можем использовать два указателя, проходясь по каждому символу в строке t и проверяя, соответствует ли он текущему символу в строке s.

Алгоритм

1. Инициализируем два указателя, один для строки s, другой для строки t с 0.
2. Пока оба указателя находятся в пределах своих строк:
   1. Если символы, на которые указывают указатели, совпадают, перемещаем указатель для s на следующий символ.
   2. Перемещаем указатель для t на следующий символ, независимо от того, совпали символы или нет.
3. Если указатель для s достиг конца строки, это означает, что s является подпоследовательностью t.

Решение

def isSubsequence(s: str, t: str) -> bool:
    pointer_s, pointer_t = 0, 0
    
    # Пока указатели в пределах своих строк
    while pointer_s < len(s) and pointer_t < len(t):
        # Если символы совпадают, перемещаем указатель для s
        if s[pointer_s] == t[pointer_t]:
            pointer_s += 1
        
        # Перемещаем указатель для t
        pointer_t += 1

    # Если указатель для s достиг конца строки, s является подпоследовательностью t
    return pointer_s == len(s)