고유한 하위 시퀀스 Leetcode

두 개의 문자열 s와 t가 주어지면 t와 같은 s의 개별 하위 시퀀스 수를 반환합니다.

문자열의 하위 시퀀스는 나머지 문자의 상대 위치를 방해하지 않고 문자 중 일부(없을 수 있음)를 삭제하여 원래 문자열에서 형성된 새 문자열입니다. (즉, "ACE"는 "ABCDE"의 하위 시퀀스이고 "AEC"는 그렇지 않습니다).

답이 부호 있는 32비트 정수에 맞도록 테스트 케이스가 생성됩니다.

예 1:

Input: s = "rabbbit", t = "rabbit"
Output: 3

설명:

As shown below, there are 3 ways you can generate "rabbit" from S.
rabbbit
rabbbit
rabbbit

class Solution {
    public int numDistinct(String s, String t) {
        // we will use little bit of backtracking here 
        int dp[][] = new int[s.length()][t.length()];
        for(int row[] : dp) Arrays.fill(row, -1);
        return distinctCount(s,t,s.length()-1,t.length()-1,dp);
    }
    public int distinctCount(String s, String t, int i,int j,int dp[][]){
        //base case
        if(i=0 && j=0 && s.charAt(i)==t.charAt(j)) return 1;
        if(j<0) return 1;
        if(i<0) return 0;
        if(dp[i][j]!=-1) return dp[i][j];
        if(s.charAt(i)==t.charAt(j)){
            // so basically if its a, match , we will either reduce s and t index both or we will just reduce the index of  s only.
            // in both the case we will return the sum of values that we get.
            return dp[i][j]= distinctCount(s,t,i-1,j-1,dp) + distinctCount(s,t,i-1,j,dp);
        }
        else{
            // else if its not a match we will have to reduce the s string index so 
            //as to reach to an index of s where s.charAt(i) == t.charAt(j);
            return dp[i][j] = distinctCount(s,t,i-1,j,dp);
        }
    }
}