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];

 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

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

  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]

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]