[leetcode] Distinct Subsequence | rabbit在rabbbit出现里几次（后者可以删除任意个字符）

Posted by: lexigrey on: October 12, 2013

• In: leetcode
• 3 Comments

这是好难好难的二维DP题。尽管知道两个String比较很可能是二维DP，但是状态方程真是不好定义；定义了关系也特别不直观。

A: RABBBIT; B: RABBIT

• d[i][j]: A[0…i]里面出现了几次B[0…j]，比如RAB里出现了几次RA
• d[i][j] =
  • if A[i] != B[j]，比如RABC和RAB，那么C(A[i]就得被删除，d[i][j]就是RAB在RAB包含的之前算过的情况d[i – 1][j]
  • if A[i] == B[j]，比如RABB和RAB，那么
    1. 可以把RABB的第二个B删除得到RAB，所以d[i][j]最少也是d[i – 1][j]
    2. 可以用RABB的第二个B直接对应RAB的那个B消掉，所以相当于A=RAB和B=RA，d[i][j] += d[i – 1][j – 1]
  • 初始值就是二维DP那么做就行了。
• 这个是真心难想通。还得多做多练习。

public int numDistinct(String S, String T) {
  if (T.length() > S.length())
    return 0;
  char[] A = S.toCharArray();
  char[] B = T.toCharArray();
  int[][] d = new int [A.length][B.length];
  d[0][0] = A[0] == B[0] ? 1 : 0;
  int count = d[0][0];
  for (int i = 1; i < A.length; i++) {
    if (A[i] == B[0])
    count++;
    d[i][0] = count;
  }
  for (int j = 1; j < B.length; j++) {
    d[0][j] = 0;
  }
  for (int i = 1; i < A.length; i++) {
    for (int j = 1; j < B.length; j++) {
      if (A[i] == B[j]) {
        d[i][j] = d[i - 1][j] + d[i - 1][j - 1];
      } else {
        d[i][j] = d[i - 1][j];
      }
    }
  }
  return d[A.length - 1][B.length - 1];
}

Tags: 2WayDP, hard, string