My O(n*m) solution for your reference


  • 6
    Y
    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].


  • 2
    R

    What about this one??

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

  • 0
    M

    I think yours are a little easier to understand


  • 0
    R

    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])
                    {
                        int toAdd = previous;
                        previous = trackers[tidx];
                        trackers[tidx]+= toAdd;
                    }
                    else
                    {
                        previous = trackers[tidx];
                    }
                }
            }
            
            int result = trackers[T.length() - 1];
            
            delete trackers;
            
            return result;
        }
    };

  • 0
    Z
    This post is deleted!

Log in to reply
 

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