Is Subsequence

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

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

Q: Почему жадный подход с двумя указателями работает для задачи Is Subsequence?

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

Q: Как быстро проверить много строк на соответствие одному и тому же t?

Подготовь t один раз: для каждой буквы сохрани отсортированный список индексов, где она встречается. Чтобы разместить s[i] , выполни двоичный поиск в списке этой буквы, чтобы найти первый индекс после предыдущего совпадения. Тогда каждая проверка будет выполняться за O(n log m) вместо O(m) .

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

+10

Даны две строки: s и t. Верните true, если можно превратить t в s, удалив некоторые её буквы (возможно, ни одной) и сохранив порядок оставшихся букв, и 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. Буквы между ними удаляются.

+20 скрытых тестов при отправке

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

Предположим, t остаётся неизменным, а тебе нужно проверить относительно него миллион разных строк s. Как подготовить t, чтобы каждая проверка выполнялась быстрее, чем повторное чтение всего t?

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

Задай вопрос поменьше: входят ли первые i букв s в первые j букв t? Назовём ответ dp[i][j]. Если они входят в t[:j-1], то входят и в t[:j], поскольку можно удалить t[j-1]. Если s[i-1] равно t[j-1], можно также использовать эту букву, и тогда первые i-1 букв s должны входить в t[:j-1]. Значит, dp[i][j] = dp[i][j-1] or (s[i-1] == t[j-1] and dp[i-1][j-1]), а пустой префикс s входит куда угодно.

Строка 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]

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

Идея

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

Почему безопасно брать первое совпадение? Предположим, что в некотором допустимом размещении используется более поздняя копия s[i]. Если заменить её самой ранней копией, порядок сохранится, а справа останется больше букв t для остальных букв s. Поэтому жадный выбор никогда не лишает нас существующего размещения. Для moon в monsoon указатель берёт o с индексом 1, пропускает n и s, берёт o с индексом 4 и останавливается на n с индексом 6.

j посещает каждую букву t один раз, а i только движется вперёд, поэтому цикл выполняется не более m раз. Для этого алгоритму нужны всего два индекса.

Алгоритм

Задай 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: в moon есть только одна n, с индексом 3, и она не может быть одновременно первой и последней буквой noon.
Возврат значения, показывающего, достиг ли j конца t. Цикл часто заканчивается на этом месте независимо от того, найдена ли s; это показывает только i.
Забывать, что s может быть длиннее t. Для abc и ab нужно вернуть false, и цикл делает это, если останавливается, когда в t заканчиваются символы.
Чтение s[i] после того, как i достиг конца s. В Python или Java такое чтение вызывает исключение, поэтому перед сравнением проверьте i.

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

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

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

Почему жадный подход с двумя указателями работает для задачи Is Subsequence?

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

Как быстро проверить много строк на соответствие одному и тому же t?

Подготовь t один раз: для каждой буквы сохрани отсортированный список индексов, где она встречается. Чтобы разместить s[i], выполни двоичный поиск в списке этой буквы, чтобы найти первый индекс после предыдущего совпадения. Тогда каждая проверка будет выполняться за O(n log m) вместо O(m).

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

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

Python

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

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

Случай 1

Случай 2

Случай 3

Ввод

s = "ace"
t = "abcde"

Ожидается

true