Lexi's Leetcode solutions

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

Posted on: October 12, 2013

这是好难好难的二维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];
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: