Сложность: 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) и возвращаем это значение в качестве ответа.
😎 Решение:
var numDistinct = function (s, t) {
let memo = new Map();
function dp(i, j) {
if (i === s.length || j === t.length || s.length - i < t.length - j)
return j === t.length ? 1 : 0;
let key = [i, j].toString();
if (memo.has(key)) return memo.get(key);
let ans = dp(i + 1, j);
if (s[i] === t[j]) ans += dp(i + 1, j + 1);
memo.set(key, ans);
return ans;
}
return dp(0, 0);
};Ставь 👍 и забирай 📚 Базу знаний