115. Distinct Subsequences

public class Solution {
    private Dictionary<string, int> memo;
    public int NumDistinct(string s, string t) {
        if (s.Length < t.Length)
            return 0;
        if (s == t || t == "")
            return 1;
        memo = new Dictionary<string, int>();
        return DistinctHelper(s.Substring(0, s.Length - 1), t) +
               ((s[s.Length - 1] == t[t.Length - 1])
                    ? DistinctHelper(s.Substring(0, s.Length - 1),
                                     t.Substring(0, t.Length - 1))
                    : 0);
    }
    private int DistinctHelper(string s, string t) {
        if (memo.ContainsKey(s + "," + t))
            return memo[s + "," + t];
        if (s.Length < t.Length)
            return 0;
        if (s == t || t == "")
            return 1;
        memo[s + "," + t] = DistinctHelper(s.Substring(0, s.Length - 1), t) +
                            ((s[s.Length - 1] == t[t.Length - 1])
                                 ? DistinctHelper(s.Substring(0, s.Length - 1),
                                                  t.Substring(0, t.Length - 1))
                                 : 0);
        return memo[s + "," + t];
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private unordered_map<string, int> memo;
    public int NumDistinct(string s, string t) {
        if (s.size() < t.size())
            return 0;
        if (s == t || t == "")
            return 1;
        memo = new unordered_map<string, int>();
        return DistinctHelper(s.Substring(0, s.size() - 1), t) +
               ((s[s.size() - 1] == t[t.size() - 1])
                    ? DistinctHelper(s.Substring(0, s.size() - 1),
                                     t.Substring(0, t.size() - 1))
                    : 0);
    }
    private int DistinctHelper(string s, string t) {
        if (memo.count(s + "," + t))
            return memo[s + "," + t];
        if (s.size() < t.size())
            return 0;
        if (s == t || t == "")
            return 1;
        memo[s + "," + t] = DistinctHelper(s.Substring(0, s.size() - 1), t) +
                            ((s[s.size() - 1] == t[t.size() - 1])
                                 ? DistinctHelper(s.Substring(0, s.size() - 1),
                                                  t.Substring(0, t.size() - 1))
                                 : 0);
        return memo[s + "," + t];
    }
}

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);
    }
}

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);
};

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)

func numDistinct(s string, t string) int {
    memo := make(map[string]int)
    var helper func(i int, j int) int
    helper = func(i int, j int) int {
        if i == len(s) || j == len(t) || len(s)-i < len(t)-j {
            if j == len(t) {
                return 1
            }
            return 0
        }
        key := strconv.Itoa(i) + "," + strconv.Itoa(j)
        if val, ok := memo[key]; ok {
            return val
        }
        ans := helper(i+1, j)
        if s[i] == t[j] {
            ans += helper(i+1, j+1)
        }
        memo[key] = ans
        return ans
    }
    return helper(0, 0)
}

Algorithm

1️⃣

Определите функцию с названием recurse, которая принимает два целочисленных значения i и j. Первое значение представляет текущий обрабатываемый символ в строке S, а второе - текущий символ в строке T. Инициализируйте словарь под названием memo, который будет кэшировать результаты различных вызовов рекурсии.**

2️⃣

Проверьте базовый случай. Если одна из строк закончилась, returnsся 0 или 1 в зависимости от того, удалось ли обработать всю строку T или нет. Есть ещё один базовый случай, который следует рассмотреть. Если оставшаяся длина строки S меньше, чем у строки T, то совпадение невозможно. Если это обнаруживается, то рекурсия также обрезается и returnsся 0.**

3️⃣

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

😎