C# Time O(m*n) Space O(n)


  • 0
    L
    public int NumDistinct(string s, string t) {
        if(s.Length < t.Length) return 0;
        int[] dp = new int[s.Length];
        for(int i = 0, lasttmpDP = 0; i < t.Length; i++){
            for(int j = 0; j < s.Length; j++){
                int tmpDP = dp[j];
                if(s[j] == t[i]){
                    if(i == 0 && j == 0) dp[j] = 1;
                    else if(i == 0) dp[j] = dp[j - 1] + 1;
                    else if(j == 0) dp[j] = 0;
                    else dp[j] = lasttmpDP + dp[j - 1];
                }
                else dp[j] = j == 0 ? 0 : dp[j - 1];
                lasttmpDP = tmpDP;
            }
        }
        return dp[s.Length - 1];
    }

Log in to reply
 

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