leetcode97-交错字符串

交错字符串

• dp

定义一个二维的dp数组，表示s1选取 i 个字符和s2选取 j 个字符组成s3的前 i+j 个字符能否成立。

dp递归方程：

1. 如果i == 0 && j == 0，表示没有任何字符，true
2. 如果i == 0，那么dp[i][j] = dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1)，dp状态取决于s2的字符和s3的字符是否相同
3. 如果j == 0，那么dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)，dp状态取决于s1的字符和s3的字符是否相同
4. 如果 i 和 j 都不等于0，那么s3当前的字符是s1或s2，两个二选一，只要有一个为true则dp状态为true

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length(), mn = s3.length();
        if(m+n != mn)   return false;
        boolean dp[][] = new boolean[m+1][n+1];
        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= n; j++){
                if(i == 0 && j == 0)    dp[i][j] = true;
                else if(i == 0) dp[i][j] = dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1);
                else if(j == 0) dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1);
                else dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)) || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1));
            }
        }
        return dp[m][n];
    }
}