LeetCode | Distinct Subsequences

题目

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

动态规划的经典题目了，找到递推关系后，仍然需要注意实现方法，这里列出了逐步优化的三种方法：

解法1：基于备忘录的递归方法，能AC，但是效率不高；

解法2：用表格的方法画出递推关系后，可以写出非递归的方法，但是需要O(n^2)的空间复杂度；

解法3：进一步分析递推关系（仔细看看画出的递推表格），可以发现在实现非递归的方法时，只需要一维数组就足够了，即O(n)的空间复杂度。

解法1

import java.util.HashMap;
import java.util.Map;

public class DistinctSubsequences {
	private char[] sCharArray;
	private char[] tCharArray;
	private int M;
	private int N;
	private Map
  
    records;

	public int numDistinct(String S, String T) {
		M = S.length();
		N = T.length();
		if (N > M) {
			return 0;
		}
		sCharArray = S.toCharArray();
		tCharArray = T.toCharArray();
		records = new HashMap
   
    (); return solve(0, 0); } private int solve(int m, int n) { int key = M * m + n; if (records.containsKey(key)) { return records.get(key); } if (n >= N) { records.put(key, 1); return 1; } if (m >= M) { records.put(key, 0); return 0; } for (int i = m; i < M; ++i) { if (sCharArray[i] == tCharArray[n]) { int result = solve(i + 1, n + 1) + solve(i + 1, n); records.put(key, result); return result; } } return 0; } }
   
  

public class DistinctSubsequences {
	public int numDistinct(String S, String T) {
		int M = S.length();
		int N = T.length();
		if (N > M) {
			return 0;
		}

		int[][] dp = new int[M + 1][N + 1];
		// init
		for (int i = N; i < M + 1; ++i) {
			dp[i][N] = 1;
		}

		// dp
		for (int i = M - 1; i >= 0; --i) {
			for (int j = (i >= N - 1   N - 1 : i); j >= 0; --j) {
				dp[i][j] = dp[i + 1][j]
						+ (S.charAt(i) == T.charAt(j)   dp[i + 1][j + 1] : 0);
			}
		}

		return dp[0][0];
	}
}

public class DistinctSubsequences {
	public int numDistinct(String S, String T) {
		int M = S.length();
		int N = T.length();
		if (N > M) {
			return 0;
		}

		int[] dp = new int[N + 1];
		// init
		dp[N] = 1;

		// dp
		for (int i = M - 1; i >= 0; --i) {
			for (int j = 0; j <= (i >= N - 1   N - 1 : i); ++j) {
				dp[j] = dp[j] + (S.charAt(i) == T.charAt(j)   dp[j + 1] : 0);
			}
		}

		return dp[0];
	}
}