Distinct Subsequences

Q:
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是基础------------------------
 ？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

Mistakes:
1: 我fuck，  想取String 的charAt方法，结果随手根据提示弄成了indexOf().  返回都是-1啊，当然相同啦。  郁闷~~~~~耽误了好几个小时。 啊啊啊啊啊啊啊啊啊啊啊啊


Learned:
1： 先把问题想清楚了，再动手。  否则， 容易，困住自己的头脑