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
.A:
------------3 rd ----------1D rolling talbe --------------------
Idea:
for each substring of T, str = T.substring(0,i); i = 1,2,... T.length();
哎,一开始非想用一个1D array,结果总是没有搞成。 费了爷们儿一个番茄。 外加吓得我一天没动手写Leetcode,哎, 还是不够勇敢阿。Tiger
下面的代码,是用了2个 一维数组, 一个记录上一次,对前一个T的字串的匹配结果(上一次的arr[j-1]。另一个计算当前的结果。(其实,就是arr[j] = arr[j-1] )。 但是由于两个索取了同一个 j-1的位置, 因此,逼得爷们儿走了2个。
还好,下面的代码,在LC 上写乱了。到Eclipse上一遍过。
public class Solution { // use rolling table // increase T, and find the number of map in S public int numDistinct(String S, String T) { int n = S.length(); int m = T.length(); if (n < m || m == 0) return 0; int[] arrCurrent = new int[n + 1]; // adding one to avoid dealing with // the boundary case int[] arrLast = new int[n + 1]; // mark the match case for the first char in T for (int j = 1; j <= S.length(); j++) { arrLast[j] = arrLast[j - 1]; if (S.charAt(j - 1) == T.charAt(0)) arrLast[j]++; } // for the next chars in T for (int i = 1; i < m; i++) { char curChar = T.charAt(i); for (int j = 1; j <= n; j++) { arrCurrent[j] = arrCurrent[j - 1]; if (curChar == S.charAt(j - 1)) { arrCurrent[j] += arrLast[j - 1]; } } // swap the pointer to two array int[] tmp = arrLast; arrLast = arrCurrent; arrCurrent = tmp; // set current array as zero Arrays.fill(arrCurrent, 0); } return arrLast[n]; } }
---------------------------------------改进--------------------
这次只用1个数组。 对于上次的match的问她用个 变量来保存。
注意: 这里的保存,需要用2个变量。 在计算一个的时候,要先把它保存下来,(放在tmpLastMatch里)
public class Solution { public int numDistinct(String S, String T) { if(S.length()==0 || S.length()<T.length()) return 0; int[] A = new int[T.length()]; for(int i =0;i<S.length();i++){ char newCh = S.charAt(i); int lastPre = 1;// for(int j = 0;j < T.length();j++){ int tmp = A[j]; if(newCh == T.charAt(j)){ A[j] += lastPre; } lastPre = tmp; } } return A[T.length() - 1]; } }
--------------------这个方法, 循环调用,比较SB------ exceed time limits-----
public class DistinctSubsequences { public int numDistinct(String S, String T) { if (S.length() < T.length()) { // no match could be found return 0; // Integer.MIN_VALUE; } return numDistinctWithIndex(S, 0, T, 0); } private int numDistinctWithIndex(String S, int startS, String T, int startT) { if (startT >= T.length()) { return 1;// all characters in T have been found, } // if S reach his end, then no match could be found ,return if (startS >= S.length()) { return 0; } if (S.charAt(startS) == T.charAt(startT)) { // if first letter are the same int a = numDistinctWithIndex(S, startS + 1, T, startT + 1);//exclude both first letter int b = numDistinctWithIndex(S, startS + 1, T, startT );//exclude the first one of S return a+b; }else{ return numDistinctWithIndex(S, startS + 1, T, startT ); } } }--------------第二遍 ,创建了个2D matrix来, 有点儿 动态规划的感觉,-----直接pass, 赞一个,哈哈--------
public class Solution { public int numDistinct(String S, String T) { // recursive solution would exceed time limit int n = S.length(); int m = T.length(); if( n<m || n == 0 ){ return 0; } if(m ==0){ // if T is empty return 1; } // now n ,m are all valid int[][] A = new int[m][n]; // A[i][j] is how many distinct count that S[0..j] lies in T[0...i] // calculate the first line A[0][0] = S.charAt(0) == T.charAt(0)?1:0; for(int j =1;j<n;j++){ A[0][j] = A[0][j-1]; if( S.charAt(j) == T.charAt(0)) A[0][j] ++; } for(int i = 1; i<m;i++){ for(int j = i; j<n;j++){ A[i][j] = A[i][j-1]; if(S.charAt(j) == T.charAt(i)) A[i][j] += A[i-1][j-1]; } } return A[m-1][n-1]; } }
---------还一个可能的方法, 基于suffix tree,从后向前调用,因为, 所有后面的,是前面char是基础------------------------
???????????????????????????????
1: 我fuck, 想取String 的charAt方法,结果随手根据提示弄成了indexOf(). 返回都是-1啊,当然相同啦。 郁闷~~~~~耽误了好几个小时。 啊啊啊啊啊啊啊啊啊啊啊啊
Learned:
1: 先把问题想清楚了,再动手。 否则, 容易,困住自己的头脑
No comments:
Post a Comment