# Double Sequence

## 1540t Can Convert

Given two string S and T, determine if S can be changed to T by deleting some letters (including 0 letter)

* Statement: 從s前i個組成的string是否可以轉成t前j個組成的string
* Func: if s\[i] == t\[j] -> dp\[i]\[j] |= dp\[i-1]\[j-1], else dp\[i]\[j] |= dp\[i-1]\[j];

```java
 public boolean canConvert(String s, String t) {
    if(s == null || t == null || s.length() == 0) return false;
    int m = s.length();
    int n = t.length();

    boolean[][] dp = new boolean[m+1][n+1];

    for(int i=0; i<=m; i++){
        dp[i][0] = true;
    }

    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){           
            if(s.charAt(i-1) == t.charAt(j-1)) dp[i][j] |= dp[i-1][j-1];                   
                         // delete
            else dp[i][j] |= dp[i-1][j];
        }
    }

    return dp[m][n];
}
```

## Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

Example Given S = "rabbbit", T = "rabbit", return 3.

* State: f\[i]\[j]表示S中前i個子串可以選出T前j個子串的個數
*   Func: f\[i]\[j] = f\[i-1]\[j-1]+f\[i-1]\[j] if S\[i-1]==T\[j-1]

    else f\[i]\[j] = f\[i-1]\[j]
* Init: f\[i]\[0] = 1, f\[0]\[j] = 0

```java
public int numDistinct(String S, String T) {
    int m = S.length();
    int n = T.length();

    int[][] f = new int[m+1][n+1];

    for(int i=0; i<=m; i++){
        f[i][0] = 1;
    }

    for(int j=1; j<=n; j++){
        f[0][j] = 0;
    }

    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(S.charAt(i-1) == T.charAt(j-1)){
                f[i][j] = f[i-1][j] + f[i-1][j-1];
            }else{
                f[i][j] = f[i-1][j];
            }
        }
    }

    return f[m][n];
}
```

## 97. InterLeaving String

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

* State: f\[i]\[j]表示s1前i個字符和s2前j個字符可以組成s3前i+j個字符
*   Func: f\[i-1]\[j] && s1\[i-1]==s3\[i+j-1] ||&#x20;

    f\[i]\[j-1] && s2\[j-1]==s3\[i+j-1]
* Init: f\[i]\[0] = s1\[0...i-1] = s3\[0...i-1], f\[0]\[j] = s2\[0...j-1] = s3\[0...j-1]
* Ans: f\[m]\[n]

```python
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
    n1, n2 = len(s1), len(s2)
    if n1+n2 != len(s3): return False
    dp = [[False] * (n2+1) for _ in range(n1+1)]
    dp[0][0] = True
    for i in range(1 ,n1+1): dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
    for j in range(1, n2+1): dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
        
    for i in range(1, n1+1):
        for j in range(1, n2+1):
            dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) \
                    or (dp[i][j-1] and s2[j-1] == s3[i+j-1])

    return dp[n1][n2]
```
