My easy to understand solution


  • 6
    L

    Actually, I start from S.substring(0, 1) and T.substring(0, 1). Then continue add one element to S and T.
    When I try to add S.charAt(i + 1) to S.substring(0, i + 1), and T.charAt(j + 1) to T.substring(0, j + 1).
    If S.charAt(i + 1) == T.charAt(j + 1) then the numDistinct(S.substring(0, i + 2), T.substring(0, j + 2)) should be numDistinct(S.substring(0, i + 1), T.substring(0, j + 1)) (use the new element in the sub string) + numDistinct(S.substring(0, i + 1), T.substring(0, j + 2)) (don't use the new element in the sub string).
    but if S.charAt(i + 1) != T.charAt(j + 1) then we can't use the new element in the sub string so numDistinct(S.substring(0, i + 2), T.substring(0, j + 2)) = numDistinct(S.substring(0, i + 1), T.substring(0, j + 2)).

    public int numDistinct(final String S, final String T)
       {
            final int[][] results = new int[T.length()+1][S.length()+1];
    
            for (int i = 0; i < S.length(); ++i)
            {
                results[0][i] = 1;
            }
            
            for (int i = 0; i < S.length(); ++i)
            {
                for (int j = 0; j < T.length(); ++j)
                {
                    if (S.charAt(i) == T.charAt(j))
                    {
                        results[j + 1][i + 1] = results[j][i] + results[j + 1][i];
                    }
                    else
                    {
                        results[j + 1][i + 1] = results[j + 1][i];
                    }
                }
            }
            
            return results[T.length()][S.length()];
        }

  • 2
    V

    O(n^2) Space complexity can be reduced to O(n) space complexity by allocating auxiliary space to a one dimensional array as at every step, an nth step doesn't depend on all other previous n-1 steps,it only depends on the (n-1)th step.

    class Solution {
        public:
    int numDistinct(string S, string T) {
        int m = T.length();
        int n = S.length();
        if (m > n) return 0;
        vector<int> result(m+1, 0);
        result[0] = 1;           
        for (int j = 1; j <= n; j++) {
            for (int i = m; i >= 1; i--) {  
                result[i] += (T[i-1] == S[j-1])*result[i-1];
            }
        }
        return result[m];
    }
    };

  • 0
    C

    Can I ask why do you need to iterate the inner loop in revered order? I know there must be a specific reason of doing it.


  • 0
    D

    I want to know the reason of iterating the inner loop in reverse order too.


  • 0
    L

    It took me a while to understand how this works. Note that this solution iterates columns first, instead of rows first as in the original easy-to-understand solution. When you iterate column first, the new value in each array element is dependent on the old values of this element and its previous element. That's why you need to iterate from the end.


Log in to reply
 

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