97. 交错字符串

Problem: 97. 交错字符串，记录官解。

做题历程

起初我试图使用双指针解题，但是对于一些测试用例，双指针（带有贪心思想）的解答是错误的，并且可以发现这些错误可以用回溯解决。

因此接下来我就试图用动态规划来解这个题。我想到的是用两个动态规划数组，分别记录字符串a和字符串b的当前长度，但是没做出来；后来撇了一眼官解，用的是二维数组来记录当前两字符串的长度，并优化掉其中一维，但是我自己去做还是没有做出来。

在看完官解的解答后，我发现我没做出来的原因是，我遍历的是数组c的长度，并在内层循环遍历数组a的长度，而官解遍历的是数组a和b的长度，这就导致我的写法非常难写。从中我也学习到了，动态规划的最外层循环不一定要是问题的规模大小，也可以是别的条件的规模大小。

动态规划题目找到dp数组的变化条件和循环方式可见非常重要，这两个知道后转移方程反而很容易想到。

正确思路

正如前文所述，状态转移方程就很好想出来了，如代码所示就不赘述。

复杂度

• 时间复杂度: $O(mn)$，m,n为数组a,b的长度。
• 空间复杂度: $O(m)$。

Code

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length(), t = s3.length();

        if (n + m != t) {
            return false;
        }

        boolean[] f = new boolean[m + 1];

        f[0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[j] = f[j] && s1.charAt(i - 1) == s3.charAt(p);
                }
                if (j > 0) {
                    f[j] = f[j] || (f[j - 1] && s2.charAt(j - 1) == s3.charAt(p));
                }
            }
        }

        return f[m];
    }
}