6 lines java solution O(n) space with explanation


  • 4
    F
    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
    W

    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.