My 5ms C++ solution using DP


  • 0
    T
    class Solution {
    public:
        int numDistinct(string S, string T) {
            if (T.length() == 0)
                return 1;
            if (S.length() == 0)
                return 0;
            int lenT = T.length();
            int m = 0, n = S.length() - 1;
            while (m < S.length() && S[m] != T[0])
                m++;
            while (n >= 0 && S[n] != T[lenT - 1])
                n--;
            int lenS = n - m + 1;
            if (lenS < lenT)
                return 0;
            int A[lenS][lenT];
            A[lenS - 1][lenT - 1] = 1;
            for (int i = lenS - 2; i >= 0; i--)
                A[i][lenT - 1] = A[i + 1][lenT - 1] + ((S[m + i] == T[lenT - 1]) ? 1 : 0);
            for (int j = lenT - 2; j >= 0; j--)
                A[lenS - 1][j] = 0;
                
            for (int i = lenS - 2; i >= 0; i--) {
                for (int j = lenT - 2; j >= 0; j--) {
                    if (lenS - i < lenT - j) {
                        A[i][j] = 0;
                        continue;
                    }
                    A[i][j] = A[i + 1][j] + ((S[m + i] == T[j]) ? A[i + 1][j + 1] : 0);
                }
            }
            return A[0][0];
        }
    };

Log in to reply
 

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