Easy DP Solution Using O(n) Space


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

Log in to reply
 

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