My c++ solution with DP


  • 0
    B
    class Solution {
    public:
        int numDistinct(string S, string T) {
            
            if ( S.length() == 0 || T.length() == 0 )
                return 0;
            int **a;
            a = new int*[S.length()+1];
            for ( int i = 0; i < S.length()+1; i++ )
                a[i] = new int[T.length()+1];
                
            for ( int i = 0; i < S.length()+1; i++ )
                a[i][0] = 0;
            for ( int i = 0; i < T.length()+1; i++ )
                a[0][i] = 0;
                
            for ( int i = 1; i < S.length()+1; i++ ) {
                for ( int j = 1; j < T.length()+1; j++ ) {
                    
                    if ( S[i-1] == T[j-1] ) {
                        
                        if ( j == 1 )
                            a[i][j] = a[i-1][j] + 1;
                        else
                            a[i][j] = a[i-1][j]+a[i-1][j-1];
                    }
                    else 
                        a[i][j] = a[i-1][j];
                }
            }
            return a[S.length()][T.length()];
        }
    };

Log in to reply
 

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