Задача: 115. Distinct Subsequences
Сложность: 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, то сoвпадение невозможно. Если это обнаруживается, то рекурсия также обрезается и возвращается 0.**

3⃣Затем проверяем, существует ли текущая пара индексов в нашем словаре. Если да, то просто возвращаем сохранённое/кэшированное значение. Если нет, то продолжаем обычную обработку. Сравниваем символы s[i] и t[j]. Сохраняем результат вызова recurse(i + 1, j) в переменную. Как упоминалось ранее, результат этой рекурсии необходим, независимо от совпадения символов. Если символы совпадают, добавляем к переменной результат вызова recurse(i + 1, j + 1). Наконец, сохраняем значение этой переменной в словаре с ключом (i, j) и возвращаем это значение в качестве ответа.**

😎 Решение:

class Solution {
    private HashMap<Pair<Integer, Integer>, Integer> memo;

    private int recurse(String s, String t, int i, int j) {
        int M = s.length();
        int N = t.length();

        if (i == M || j == N || M - i < N - j) {
            return j == t.length() ? 1 : 0;
        }

        Pair<Integer, Integer> key = new Pair<Integer, Integer>(i, j);

        if (this.memo.containsKey(key)) {
            return this.memo.get(key);
        }

        int ans = this.recurse(s, t, i + 1, j);

        if (s.charAt(i) == t.charAt(j)) {
            ans += this.recurse(s, t, i + 1, j + 1);
        }

        this.memo.put(key, ans);
        return ans;
    }

    public int numDistinct(String s, String t) {
        this.memo = new HashMap<Pair<Integer, Integer>, Integer>();
        return this.recurse(s, t, 0, 0);
    }
}

Ставь 👍 и забирай 📚 Базу знаний