# My O(n*m) solution for your reference

• ``````public int numDistinct(String S, String T) {
if(S==null || T==null)return 0;
int occu[]=new int[T.length()];
for(int i=S.length()-1;i>=0;i--){
for(int j=0;j<T.length();j++){
if(S.charAt(i)==T.charAt(j)){
if(j==(T.length()-1))occu[j]++;
else occu[j]+=occu[j+1];
}
}
}
return occu[0];
}
``````

Basically the idea is iterate from the end of S, and if S.charAt(i) == T.charAt(j), then the distinct sub sequences of T.substring(j) in S.substring(i) can be calculated as occu[j]=occu[j]+occu[j+1]. The final result is occu[0].

``````public class Solution {
public int numDistinct(String S, String T) {

int short_length=T.length();
int long_length=S.length();
if (short_length>long_length) return 0;

int[] array = new int[short_length+1];

Arrays.fill(array,0);

array[0]=1;

for (int i =1;i<=long_length;i++)
for (int j =short_length;j>=1;j--)
if (T.charAt(j-1)==S.charAt(i-1))
array[j]+=array[j-1];

return array[short_length];

}
}``````

• I think yours are a little easier to understand

• This is similar to reeclapple one but it becomes O(n) if there is not matches and goes towards O(n*m) if there are matches.

``````class Solution {
public:
int numDistinct(string S, string T) {
size_t Slength = S.length();
size_t Tlength = T.length();

if (!Slength || !Tlength || Tlength > Slength) return 0;

// trackers[0] if S[idx] == T[0] then trackers[0]++
// trackers[1] if S[idx] == T[1] then trackers[1]+= trackers[0]
// trackers[n] if S[idx] == T[n] then trackers[n]+= trackers[n-1]
// trackers[T.length() - 1] will have the result.
//
int* trackers = new int[Tlength + 1];
memset(trackers, 0, sizeof(int) * (Tlength+1));

int numberOfDistinct = 0;

for (int idx= 0; idx < Slength; ++idx)
{
int previous = 1;
for(int tidx = 0; previous; tidx++)
{
if (S[idx] == T[tidx])
{
previous = trackers[tidx];
}
else
{
previous = trackers[tidx];
}
}
}

int result = trackers[T.length() - 1];

delete trackers;

return result;
}
};``````

• This post is deleted!

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