Число различных подпоследовательностей
Hard
Даны строки
Иначе: сколько раз
s и t. Сколько различных способов выбрать возрастающие индексы в s, чтобы образовалась строка t?Иначе: сколько раз
t встречается в s как подпоследовательность (не обязательно непрерывная подстрока). Разные наборы позиций считаются разными способами. Если t пуста, обычно считается один способ (выбрать пустой набор индексов).Примеры:
Вход:
{"s": "rabbbit", "t": "rabbit"}
Выход:
3
Объяснение: s='rabbbit', t='rabbit': три буквы 'b' в s дают три разных способа выбрать две нужные 'b' для t → 3.
Вход:
{"s": "babgbag", "t": "bag"}
Выход:
5
Объяснение: s='babgbag', t='bag': подпоследовательность 'bag' можно выбрать пятью разными наборами позиций → 5.
Вход:
{"s": "", "t": ""}
Выход:
1
Объяснение: s='' и t='': пустая подпоследовательность пустой строки — 1 способ.
Ограничения:
0 <= s.length <= 1000
0 <= t.length <= 1000
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!