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

Решение: Проверка на подпоследовательность

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

Определение подпоследовательности

• Подпоследовательность НЕ требует смежности элементов
• Порядок символов ДОЛЖЕН сохраняться
• Пустая строка всегда подпоследовательность любой строки

Примеры:

• "abc" — подпоследовательность "ahbgdc" (a_b_c)
• "axc" — НЕ подпоследовательность "ahbgdc" (нет x)
• "" — подпоследовательность любой строки

Алгоритм (двухточечный подход)

1. Инициализируем два указателя: i = 0 (для s), j = 0 (для t)
2. Проходим по строке t:
   • Если текущий символ из t совпадает с текущим символом из s:

     - Двигаем указатель s на один шаг вперёд

• Всегда двигаем указатель t на один шаг вперёд

1. Если i достигла конца s — s является подпоследовательностью t
2. Иначе — s не является подпоследовательностью t

Реализация (двухточечный подход)

def isSubsequence(s: str, t: str) -> bool:
    """
    Проверяет, является ли строка s подпоследовательностью строки t.
    
    Args:
        s: Потенциальная подпоследовательность
        t: Основная строка
    
    Returns:
        True, если s является подпоследовательностью t, иначе False
    """
    i = 0  # Указатель для s
    j = 0  # Указатель для t
    
    # Проходим по строке t
    while i < len(s) and j < len(t):
        # Если символы совпадают, двигаем указатель s
        if s[i] == t[j]:
            i += 1
        # Всегда двигаем указатель t
        j += 1
    
    # s является подпоследовательностью, если мы прошли всю строку s
    return i == len(s)

Пошаговый разбор примеров

Пример 1: s = "abc", t = "ahbgdc"

Шаг 0:

s = "abc", t = "ahbgdc"
i = 0, j = 0

Шаг 1: t[0] = a, s[0] = a

Совпадение! i = 1, j = 1

Шаг 2: t[1] = h, s[1] = b

Не совпадает. j = 2

Шаг 3: t[2] = b, s[1] = b

Совпадение! i = 2, j = 3

Шаг 4: t[3] = g, s[2] = c

Не совпадает. j = 4

Шаг 5: t[4] = d, s[2] = c

Не совпадает. j = 5

Шаг 6: t[5] = c, s[2] = c

Совпадение! i = 3, j = 6

Цикл завершился: i = 3 = len(s) → Возвращаем True ✓

Пример 2: s = "axc", t = "ahbgdc"

Шаг 1: t[0] = a, s[0] = a → Совпадение, i = 1 Шаг 2: t[1] = h, s[1] = x → Нет совпадения Шаг 3: t[2] = b, s[1] = x → Нет совпадения Шаг 4: t[3] = g, s[1] = x → Нет совпадения Шаг 5: t[4] = d, s[1] = x → Нет совпадения Шаг 6: t[5] = c, s[1] = x → Нет совпадения

Цикл завершился: i = 1 ≠ 3 = len(s) → Возвращаем False ✓

Альтернативное решение с итератором

def isSubsequence_iterator(s: str, t: str) -> bool:
    """
    Версия с использованием встроенных функций Python
    """
    it = iter(t)
    # Проверяем, найдётся ли каждый символ из s в t в правильном порядке
    return all(c in it for c in s)

Объяснение:

• iter(t) создаёт итератор по строке t
• c in it ищет символ c в оставшейся части итератора
• all() проверяет, что все символы из s найдены

Версия с использованием регулярных выражений

import re

def isSubsequence_regex(s: str, t: str) -> bool:
    """
    Решение с использованием регулярных выражений
    """
    pattern = ".*?".join(s)
    return bool(re.search(pattern, t))

Пример:

• s = "abc" → pattern = "a.?b.?c"
• Ищет подстроку: a, затем b (ленивый поиск), затем c

Тестовые случаи

# Основные примеры
print(isSubsequence("abc", "ahbgdc"))        # True
print(isSubsequence("axc", "ahbgdc"))        # False

# Граничные случаи
print(isSubsequence("", "ahbgdc"))           # True (пустая подпоследовательность)
print(isSubsequence("a", ""))                # False
print(isSubsequence("", ""))                 # True
print(isSubsequence("abc", "abc"))           # True (равные строки)
print(isSubsequence("abc", "ab"))            # False (t короче s)

# Специальные случаи
print(isSubsequence("a", "a"))               # True
print(isSubsequence("a", "ab"))              # True
print(isSubsequence("b", "ab"))              # True
print(isSubsequence("ba", "ab"))             # False (неверный порядок)
print(isSubsequence("aaa", "aabaa"))         # True
print(isSubsequence("aaa", "aba"))           # False

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

Сложность оптимального решения

• Временная сложность: O(n), где n = len(t)
• Пространственная сложность: O(1), используем только два указателя

Важные детали

• Порядок важен — подпоследовательность чувствительна к порядку символов
• Пустая строка всегда подпоследовательность
• Чувствительность к регистру — A ≠ a
• Пробелы — считаются полноценными символами

Двухточечный подход — оптимальное и рекомендуемое решение для production-кода благодаря простоте и эффективности.