6 lines java solution O(n) space with explanation

  • 4
    public int numDistinct(String s, String t) {
        int[] dp = new int[t.length()];
        for(int i=0; i<s.length(); i++)
            for(int j=t.length()-1; j>=0; j--)
                if(s.charAt(i) == t.charAt(j))
                    dp[j] = ( j==0 ? 1 : dp[j-1]) + dp[j];
        return dp[t.length()-1];

    define dp[i][j] as total distinct strings [0,j] of T in [0,i] of S,
    then there are two cases:

    1. dp[i][j] = dp[i-1][j] ,which means we can find [0,j] in [0,i-1].
    2. dp[i][j] = dp[i-1][j] + dp[i-1][j-1] if T[j] = S[i], either we can find [0,j] in [0,i-1], or find [0,j-1] in [0,i-1] with T[i] = S[i].

    with optimization, use one dimension and iterate back forward then

    1. dp[i] = dp[i]
    2. dp[i] = dp[i] + dp[i-1]

  • 0

    Can you explain why it's backward in the one dimension solution? Thanks

Log in to reply

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