Given two strings s and t, return the number of distinct subsequences of s which equals t.

A string’s subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters’ relative positions. (i.e., “ACE” is a subsequence of “ABCDE” while “AEC” is not).

The test cases are generated so that the answer fits on a 32-bit signed integer.

classSolution { unordered_map<char, vector<int>> seq; //index of t and select of s int dp[1001][1001]; int ma; //o(m*k * logk) //m is for iterating all idx //logk is for binary search //k is for iterating binary search solution intsolution(string& t, int idx, int mi){ if(idx == t.length()) return1; if(dp[idx][mi] != -1) return dp[idx][mi]; if(t.length() - idx > ma - mi) return0; dp[idx][mi] = 0; auto it = lower_bound(seq[t[idx]].begin(), seq[t[idx]].end(), mi); for(; it != seq[t[idx]].end(); it++) { dp[idx][mi] += solution(t,idx + 1, *it + 1); } return dp[idx][mi]; } public: //o(n + kmlogk) intnumDistinct(string s, string t){ for(int i = 0; i < s.length(); i++) { //o(n) seq[s[i]].push_back(i); } memset(dp,-1,sizeof(dp)); ma = s.length(); returnsolution(t,0,0); } };