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

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

😎 Решение:

class Solution {
    private $memo = [];

    public function numDistinct($s, $t) {
        return $this->uniqueSubsequences($s, $t, 0, 0);
    }

    private function uniqueSubsequences($s, $t, $i, $j) {
        $M = strlen($s);
        $N = strlen($t);

        if ($i == $M || $j == $N || $M - $i < $N - $j) {
            return (int)($j == strlen($t));
        }

        if (isset($this->memo["$i,$j"])) {
            return $this->memo["$i,$j"];
        }

        $ans = $this->uniqueSubsequences($s, $t, $i + 1, $j);

        if ($s[$i] == $t[$j]) {
            $ans += $this->uniqueSubsequences($s, $t, $i + 1, $j + 1);
        }

        $this->memo["$i,$j"] = $ans;
        return $ans;
    }
}

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