题目链接

97. 交错字符串

思路

分析动态规划题目的时候只需要考虑最后一个阶段，因为所有的阶段转化都是相同的，考虑最后一个阶段容易发现规律

在数组的动态规划问题中，一般 dp[i] 都是表示以 nums[i] 为结尾的状态；dp[i][j] 分别表示以 nums1[i] 和 nums2[j] 为结尾的状态，以此类推

字符串也是个数组，是字符数组

参考类似路径问题，找准状态方程快速求解

表示状态

在遇到两个数组的动态规划问题时，可以通过画矩阵直观进行分析

我们很容易想到：target 的每个字符都是从 s1（向下）或者 s2（向右）拿到的，所以只要判断是否存在这条 target 路径即可

于是我们可以定义 dp[i][j] 代表 s1 前 i 个字符与 s2 前 j 个字符能否拼接成 s3 前 i + j 个字符

找状态转移方程

边界处理

代码

`dp`数组版

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        // dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否组成 s3 的前 i + j 个字符
        int n1 = s1.length();
        int n2 = s2.length();
        if(n1 + n2 != s3.length()){
            return false;
        }
        boolean[][] dp = new boolean[n1 + 1][n2 + 1];

        dp[0][0] = true;
        for(int i = 1; i <= n1 && s1.charAt(i - 1) == s3.charAt(i - 1); i++){
            dp[i][0] = true;
        }
        for(int i = 1; i <= n2 && s2.charAt(i - 1) == s3.charAt(i - 1); i++){
            dp[0][i] = true;
        }
        for(int i = 1; i <= n1; i++){
            for(int j = 1; j <= n2; j++){
                char c1 = s1.charAt(i - 1);
                char c2 = s2.charAt(j - 1);
                char c3 = s3.charAt(i + j - 1);
                dp[i][j] = (dp[i - 1][j] && c1 == c3) || (dp[i][j - 1] && c2 == c3);
            }
        }

        return dp[n1][n2];
    }
}