Проверка на подпоследовательность

Проверка на подпоследовательность

Описание задачи

Подпоследовательность — это строка, полученная путём удаления нескольких (возможно нуля) символов из исходной строки без изменения порядка оставшихся символов.

Например:

• "abc" является подпоследовательностью "ahbgdc" (a-h-b-g-d-c → abc)
• "axc" НЕ является подпоследовательностью "ahbgdc" (нет 'x')

Это простая задача с неколькими элегантными решениями.

Подход 1: Двойной указатель (оптимальный)

Идея: проходим по обеим строкам одновременно, ищем каждый символ s в t.

def isSubsequence(s: str, t: str) -> bool:
    # Указатели на обе строки
    s_idx = 0
    t_idx = 0
    
    # Проходим по t
    while t_idx < len(t):
        # Если символы совпадают, сдвигаем указатель в s
        if s_idx < len(s) and s[s_idx] == t[t_idx]:
            s_idx += 1
        
        # Всегда сдвигаем указатель в t
        t_idx += 1
    
    # Если мы прошли все символы s, то s — подпоследовательность t
    return s_idx == len(s)

# Примеры
print(isSubsequence("abc", "ahbgdc"))   # True
print(isSubsequence("axc", "ahbgdc"))   # False
print(isSubsequence("", "ahbgdc"))      # True (пустая строка — подпоследовательность всех)
print(isSubsequence("a", "ahbgdc"))     # True
print(isSubsequence("aghd", "ahbgdc"))  # True
print(isSubsequence("acb", "ahbgdc"))   # False (c идёт после b в t)

Логика:

1. Создаём два указателя: s_idx для строки s и t_idx для строки t
2. Проходим по t слева направо
3. Если текущий символ в t совпадает с текущим символом в s:
   • Сдвигаем указатель в s (ищем следующий символ)
4. Всегда сдвигаем указатель в t (ищем в следующей позиции)
5. Если в конце s_idx == len(s), значит нашли все символы s

Сложность:

• Временная: O(n), где n — длина t (один проход)
• Пространственная: O(1) (только две переменные)

Подход 2: Генератор (Pythonic)

def isSubsequence_v2(s: str, t: str) -> bool:
    # Создаём итератор для t
    t_iter = iter(t)
    
    # Проверяем, что все символы s есть в t в правильном порядке
    return all(char in t_iter for char in s)

print(isSubsequence_v2("abc", "ahbgdc"))   # True
print(isSubsequence_v2("axc", "ahbgdc"))   # False

Как это работает:

1. t_iter — итератор для t
2. char in t_iter проходит по t и проверяет, есть ли char
3. Важно: in на итераторе не перезагружает — проходит дальше
4. all() проверяет, что все символы найдены

Это очень элегантное решение!

Подход 3: Рекурсия (понимание логики)

def isSubsequence_v3(s: str, t: str) -> bool:
    # Базовый случай: если s пуста, то она подпоследовательность
    if not s:
        return True
    
    # Если t пуста, но s не пуста — не подпоследовательность
    if not t:
        return False
    
    # Если первые символы совпадают — ищем остаток s в остатке t
    if s[0] == t[0]:
        return isSubsequence_v3(s[1:], t[1:])
    
    # Если не совпадают — ищем s в остатке t
    return isSubsequence_v3(s, t[1:])

print(isSubsequence_v3("abc", "ahbgdc"))   # True
print(isSubsequence_v3("axc", "ahbgdc"))   # False

Проблема: O(n*m) по времени (может быть медленно на больших строках)

Подход 4: Динамическое программирование

Для более сложных задач (например, подсчёт количеств подпоследовательностей):

def isSubsequence_v4(s: str, t: str) -> bool:
    m, n = len(s), len(t)
    
    # dp[i][j] — является ли s[0:i] подпоследовательностью t[0:j]
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # Пустая строка — подпоследовательность всего
    for j in range(n + 1):
        dp[0][j] = True
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                # Если символы совпадают, берём значение диагонали
                dp[i][j] = dp[i - 1][j - 1]
            else:
                # Если не совпадают, берём слева (ищем в остатке t)
                dp[i][j] = dp[i][j - 1]
    
    return dp[m][n]

print(isSubsequence_v4("abc", "ahbgdc"))   # True
print(isSubsequence_v4("axc", "ahbgdc"))   # False

Сложность: O(m*n) по времени и пространству (избыточно для этой задачи)

Тестирование

import unittest

class TestIsSubsequence(unittest.TestCase):
    def setUp(self):
        self.solution = isSubsequence
    
    def test_basic(self):
        self.assertTrue(self.solution("abc", "ahbgdc"))
        self.assertFalse(self.solution("axc", "ahbgdc"))
    
    def test_empty_s(self):
        # Пустая строка — подпоследовательность всего
        self.assertTrue(self.solution("", "hello"))
        self.assertTrue(self.solution("", ""))
    
    def test_empty_t(self):
        # Непустая строка не может быть подпоследовательностью пустой
        self.assertFalse(self.solution("a", ""))
    
    def test_both_empty(self):
        self.assertTrue(self.solution("", ""))
    
    def test_equal_strings(self):
        # Строка — подпоследовательность самой себя
        self.assertTrue(self.solution("hello", "hello"))
    
    def test_single_char(self):
        self.assertTrue(self.solution("a", "ahbgdc"))
        self.assertFalse(self.solution("x", "ahbgdc"))
    
    def test_order_matters(self):
        # Порядок символов важен!
        self.assertFalse(self.solution("bac", "ahbgdc"))  # c идёт до a
        self.assertTrue(self.solution("acb", "ahbgdc"))   # a-c-b в правильном порядке
    
    def test_duplicates(self):
        self.assertTrue(self.solution("aaa", "aaabbb"))
        self.assertFalse(self.solution("aaaa", "aaabbb"))

Визуализация (двойной указатель)

s = "abc"
t = "ahbgdc"

Шаг 1: s_idx=0, t_idx=0
  s[0]='a', t[0]='a' → совпадают! s_idx=1
  Шаг 2: s_idx=1, t_idx=1
  s[1]='b', t[1]='h' → не совпадают
  Шаг 3: s_idx=1, t_idx=2
  s[1]='b', t[2]='b' → совпадают! s_idx=2
  Шаг 4: s_idx=2, t_idx=3
  s[2]='c', t[3]='g' → не совпадают
  Шаг 5: s_idx=2, t_idx=4
  s[2]='c', t[4]='d' → не совпадают
  Шаг 6: s_idx=2, t_idx=5
  s[2]='c', t[5]='c' → совпадают! s_idx=3

В конце: s_idx=3 == len(s)=3 ✓ → True

Сравнение подходов

Практические применения

1. Проверка версий: совместима ли старая версия API с новой
2. Поиск паттернов: содержит ли текст нужную последовательность слов
3. Валидация: проверка, что пользователь ввёл правильный код в правильном порядке
4. Сжатие данных: поиск общих подпоследовательностей в строках

Заключение

Это простая, но важная задача. Двойной указатель — оптимальное решение с O(n) временем и O(1) пространством. Генератор версия показывает Pythonic подход. Важно понимать, почему in t_iter работает эффективно — потому что итератор хранит состояние между вызовами.