# 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]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://netjimmy.gitbook.io/code-interview-note/dynamic/double-sequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.