Alternative solution without using DP. Space complexity O(m). Time complexity O(m * n)

• ``````class Solution {
public:
int numDistinct(string S, string T) {
/* prefix_map maps each character of string T to a prefix in string T
* that this character can extend. For example for T = "rabbit" mapping
* will be {r -> "", a -> "r", b -> "ra, rab", i -> "rabb", t -> "rabbi"} */
unordered_multimap<char, string> prefix_map;
for (int i = 0; i < T.size(); ++i)
prefix_map.insert(make_pair(T[i], T.substr(0, i)));

/* prefix_count stores number of prefixes of T found so far. Initially
* it contains all zeros */
unordered_map<string, int> prefix_count;
for (int i = 0; i < T.size(); ++i)
prefix_count[T.substr(0, i + 1)] = 0;

/* for each character c in string S we use prefix_map to found which
* prefixes can be extended using c and update prefix_count accordingly */
for (int i = 0; i < S.size(); ++i)
{
auto range = prefix_map.equal_range(S[i]);
for (auto it = range.first; it != range.second; ++it)
{
string prefix = it->second;
string cur = prefix + S[i];

if (prefix.empty())
prefix_count[cur] += 1;
else
prefix_count[cur] += prefix_count[prefix];
}
}

return prefix_count[T];
}
};``````

• I think it's still DP. prefix_count is restoring the information before, which is just DP...

• prefix_ma needs O(N^2) space (if T is length N).

• Failed when S="eee",T="eee". This algorithm failed when there are successive characters in T.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.