[leetcode] Distinct Subsequence | rabbit在rabbbit出现里几次(后者可以删除任意个字符)
Posted October 12, 2013
on:- 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,那么
- 可以把RABB的第二个B删除得到RAB,所以d[i][j]最少也是d[i – 1][j]
- 可以用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]; }
June 27, 2014 at 9:31 pm
赞