Is Subsequence

Q: Какова временная сложность задачи «Is Subsequence»?

Решение с двумя указателями работает за время O(n + m) , где n и m — длины s и t , и использует O(1) дополнительной памяти. Цикл останавливается не более чем через m шагов. Для построения таблицы префиксов требуется время O(n × m) .

Q: Как задача «Является ли подпоследовательностью» связана с задачей о наибольшей общей подпоследовательности?

s является подпоследовательностью t тогда и только тогда, когда длина их наибольшей общей подпоследовательности равна n , то есть длине s . Таблица префиксов из первого подхода — это та таблица, которую вы строите для этой задачи. Здесь нужно знать только, помещается ли в t вся строка s , поэтому достаточно жадного прохода.

ЛегкоДва указателя

+10

Вам даны две строки: s и t. Верните true, если можно получить s из t, удалив некоторые буквы (возможно, ни одной), сохранив порядок оставшихся букв, и false в противном случае. Например, ace является подпоследовательностью abcde, а aec — нет.

Функция

isSubsequence(s: string, t: string) → boolean

sstring: строка, которую нужно найти
tstring: строка, из которой нужно удалить буквы
Возвращаетboolean: true, если s можно прочитать внутри t по порядку, возможно, с пропусками

Ограничения

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s и t содержат только строчные английские буквы.

Примеры

Ввод: s = "ace"t = "abcde"
Вывод: true
Пояснение: Удалите b и d из abcde, и останется ace в том же порядке.

Ввод: s = "aec"t = "abcde"
Вывод: false
Пояснение: В t есть все три буквы, но единственная c находится перед единственной e. После того как ты используешь e с индексом 4, справа от неё не остаётся ни одной c.

Ввод: s = "moon"t = "monsoon"
Вывод: true
Пояснение: Используйте m с индексом 0, буквы o с индексами 1 и 4 и n с индексом 6 в слове monsoon. Буквы между ними удаляются.

Дополнительный вопрос

Если t остаётся неизменной, и ты проверяешь миллион строк s на соответствие ей, как подготовить t, чтобы каждая проверка выполнялась быстрее, чем чтение всей t?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Подпоследовательность может пропускать буквы в t где угодно, поэтому может показаться, что нужно попробовать множество вариантов размещения s. Но это не нужно: сопоставлять каждую букву из s в самом раннем возможном месте всегда не хуже, чем делать любой другой выбор, поэтому достаточно одного прохода слева направо с двумя указателями.

Динамическое программирование по префиксам

Верно, но не успевает на самых больших тестах

Идея

Пусть dp[i][j] показывает, помещаются ли первые i букв s среди первых j букв t. Они помещаются, если уже помещаются и без t[j-1] либо если s[i-1] равно t[j-1] и первые i-1 букв помещаются среди t[:j-1]. Пустой префикс помещается везде, а строка i использует только строку i-1, поэтому достаточно двух строк длины m+1.

Таблица заполняет каждую ячейку: при длине s в 25,000 букв и длине t в 50,000 букв это 1.25 × 10^9 ячеек.

Алгоритм

Создай строку prev из m+1 значений, все true: пустая s подходит к каждому префиксу t.
Для каждого i от 1 до n создай строку cur с cur[0] = false.
Для каждого j от 1 до m установи cur[j] в значение cur[j-1] или prev[j-1], если s[i-1] равно t[j-1].
Замени prev на cur.
Верни prev[m].

def isSubsequence(s, t):
    n, m = len(s), len(t)
    # prev[j]: the first i-1 letters of s fit inside t[:j]. An empty s fits anywhere.
    prev = [True] * (m + 1)
    for i in range(1, n + 1):
        cur = [False] * (m + 1)
        for j in range(1, m + 1):
            cur[j] = cur[j - 1] or (s[i - 1] == t[j - 1] and prev[j - 1])
        prev = cur
    return prev[m]

Два указателя с жадным сопоставлением

Идея

Храни указатель i на следующую нужную букву в s и бери первое её вхождение, которое встретишь в t. Такой выбор безопасен. Если в допустимом размещении используется более позднее вхождение s[i], замена его на самое раннее сохраняет порядок и оставляет больше символов t для оставшейся части s. Поэтому, если существует хотя бы одно размещение, жадный алгоритм его найдёт.

Цикл читает каждую букву t не более одного раза и хранит два индекса: время O(n + m) и память O(1).

Алгоритм

Установи i = 0 для s и j = 0 для t.
Пока оба индекса находятся внутри своих строк, сравнивай s[i] с t[j].
Если они равны, увеличь i.
Увеличивай j в любом случае.
Верни результат проверки, равно ли i длине s.

def isSubsequence(s, t):
    i = j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

Ловушки и крайние случаи

Поиск каждой буквы из s где угодно в t, а не после предыдущего совпадения. Это приводит к тому, что aec считается подпоследовательностью в abcde.
Использование одной и той же буквы дважды. noon не является подпоследовательностью moon: единственная n — с индексом 3 — не может быть одновременно первой и последней буквой.
Возврат значения, показывающего, достиг ли j конца t. Цикл часто заканчивается там независимо от того, найдена ли s; только i подскажет вам это.
Продолжение работы, когда в t закончились символы. Для abc и ab нужно вернуть false.
Чтение s[i] после того, как i достиг конца s. В Python или Java такое чтение вызывает исключение, поэтому проверяйте i перед сравнением.

Частые вопросы3

Какова временная сложность задачи «Is Subsequence»?

Решение с двумя указателями работает за время O(n + m), где n и m — длины s и t, и использует O(1) дополнительной памяти. Цикл останавливается не более чем через m шагов. Для построения таблицы префиксов требуется время O(n × m).

Как задача «Является ли подпоследовательностью» связана с задачей о наибольшей общей подпоследовательности?

s является подпоследовательностью t тогда и только тогда, когда длина их наибольшей общей подпоследовательности равна n, то есть длине s. Таблица префиксов из первого подхода — это та таблица, которую вы строите для этой задачи. Здесь нужно знать только, помещается ли в t вся строка s, поэтому достаточно жадного прохода.

В чем разница между подпоследовательностью и подстрокой?

Подстрока — это блок идущих подряд букв, а подпоследовательность может пропускать буквы, если их порядок сохраняется. ace — подпоследовательность abcde, но не её подстрока. Каждая подстрока является подпоследовательностью, но не наоборот.

def isSubsequence(s, t):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

s = "ace"
t = "abcde"

Ожидаемый вывод

true