Сложность: hard
"Даны две строки s и t. Верните количество различных подпоследовательностей строки s, которые равны строке t.
Тестовые примеры сгенерированы таким образом, что ответ укладывается в 32-битное целое число со знаком."
Пример:
Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
rabbbit
rabbbit
👨💻 Алгоритм:
1️⃣Определите функцию с названием recurse, которая принимает два целочисленных значения i и j. Первое значение представляет текущий обрабатываемый символ в строке S, а второе - текущий символ в строке T. Инициализируйте словарь под названием memo, который будет кэшировать результаты различных вызовов рекурсии.**
2️⃣Проверьте базовый случай. Если одна из строк закончилась, возвращается 0 или 1 в зависимости от того, удалось ли обработать всю строку T или нет. Есть ещё один базовый случай, который следует рассмотреть. Если оставшаяся длина строки S меньше, чем у строки T, то совпадение невозможно. Если это обнаруживается, то рекурсия также обрезается и возвращается 0.**
3️⃣Затем проверяем, существует ли текущая пара индексов в нашем словаре. Если да, то просто возвращаем сохранённое/кэшированное значение. Если нет, то продолжаем обычную обработку. Сравниваем символы s[i] и t[j]. Сохраняем результат вызова recurse(i + 1, j) в переменную. Как упоминалось ранее, результат этой рекурсии необходим, независимо от совпадения символов. Если символы совпадают, добавляем к переменной результат вызова recurse(i + 1, j + 1). Наконец, сохраняем значение этой переменной в словаре с ключом (i, j) и возвращаем это значение в качестве ответа.
😎 Решение:
class Solution:
def numDistinct(self, s: str, t: str) -> int:
memo = {}
def uniqueSubsequences(i: int, j: int) -> int:
M, N = len(s), len(t)
if i == M or j == N or M - i < N - j:
return int(j == len(t))
if (i, j) in memo:
return memo[i, j]
ans = uniqueSubsequences(i + 1, j)
if s[i] == t[j]:
ans += uniqueSubsequences(i + 1, j + 1)
memo[i, j] = ans
return ans
return uniqueSubsequences(0, 0)
Ставь 👍 и забирай 📚 Базу знаний