В этой статье мы подробно разберем решение задачи "Is Subsequence" с платформы NeetCode. Рассмотрим базовое решение с двумя указателями, альтернативные подходы и критически важную оптимизацию для сценария с миллиардами запросов .
Постановка задачи
Условие:
Даны две строки s и t. Нужно определить, является ли s подпоследовательностью t.
Подпоследовательность — строка, образованная из исходной путем удаления некоторых символов без изменения относительного порядка оставшихся символов.
Примеры:
s = "ace", t = "abcde" → true
Объяснение: берем символы t[0]='a', t[2]='c', t[4]='e' → "ace"
s = "aec", t = "abcde" → false
Объяснение: 'e' в t находится после 'c', но в s 'e' идет перед 'c' → порядок нарушен
s = "node", t = "neetcode" → true
Объяснение: n(0), o(2), d(5), e(6) → "node"
s = "axc", t = "ahbgdc" → false
Объяснение: 'a' найден, 'x' не найден после 'a'
Ограничения:
- 0 <= s.length <= 100
- 0 <= t.length <= 10,000
- Строки содержат только строчные английские буквы
Follow-up (ключевой вопрос для сеньора):
Если нужно проверить миллиарды строк s относительно одной строки t, как оптимизировать решение?
Подход 1: Два указателя (базовое решение)
Идея алгоритма
Используем два указателя:
- i — для прохода по строке s (подпоследовательность)
- j — для прохода по строке t (исходная строка)
Алгоритм:
- Проходим по t символ за символом
- Если текущий символ t[j] совпадает с s[i] — двигаем оба указателя
- Если не совпадает — двигаем только j
- Если дошли до конца s (i == s.length()) — s является подпоследовательностью
Реализация на Java 11
Подход 2: Оптимизация для миллиардов запросов
Проблема базового подхода
При миллиардах запросов (k >= 1,000,000,000):
- Для k = 10⁹ и m = 10⁴ → 10¹³ операций (неприемлемо даже на суперкомпьютере)
Решение: Предварительная обработка строки t
Создадим структуру данных для быстрого поиска следующего вхождения символа после заданной позиции.
Шаг 1: Построение маппинга символ → список позиций
Для t = "neetcode":
'n' → [0]
'e' → [1, 2, 5, 6]
't' → [3]
'c' → [4]
'o' → [7]
'd' → [8]
Шаг 2: Бинарный поиск для каждого символа s
Для каждого символа в s ищем минимальную позицию в t, которая больше текущей позиции.
Полная реализация для миллиардов запросов
Визуализация оптимизированного подхода
Для t = "neetcode" и запроса s = "node":
Предварительная обработка t:
'n' → [0]
'o' → [7]
'd' → [8]
'e' → [1, 2, 5, 6]
...
Запрос s = "node":
1. 'n': ищем позицию > -1 → [0] → берем 0, текущая позиция = 0
2. 'o': ищем позицию > 0 → [7] → берем 7, текущая позиция = 7
3. 'd': ищем позицию > 7 → [8] → берем 8, текущая позиция = 8
4. 'e': ищем позицию > 8 → [] (все 'e' до позиции 8) → не найдено → false?
Ошибка! В "neetcode" после 'd' (позиция 8) нет 'e' → но "node" НЕ подпоследовательность "neetcode"?
Проверка: n(0), o(7), d(8) — после позиции 8 нет 'e' → действительно не подпоследовательность!
Но в условии задачи: s = "node", t = "neetcode" → true
Разбор "neetcode":
n e e t c o d e
0 1 2 3 4 5 6 7 ← индексы (исправлено!)
Правильные позиции:
'n' → [0]
'e' → [1, 2, 7]
't' → [3]
'c' → [4]
'o' → [5]
'd' → [6]
Запрос "node":
'n' → 0
'o' → первая позиция > 0 → 5
'd' → первая позиция > 5 → 6
'e' → первая позиция > 6 → 7 → найдено!
Результат: true
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/neetcode/tree/main/src/main/java/IsSubsequence