题目描述

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

样例

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

算法分析

动态规划

注意：此题不能使用双指针算法，假设当前a指针指向的是s1下一个枚举的字符的位置，b指针指向的是s2下一个枚举的字符的位置，c指针指向的是s3当前枚举到的字符的位置，c指向的元素是给a用还是给b用，c后面的字符的分配情况都会导致匹配的失败，例如s1是b，s2是ab,s3是bab，若s3第一个b给了s1用，则会导致不匹配，给s2用才匹配，又如何想出怎么样的分配顺序，还是很难的，可是分配的情况可以看成一个集合，从集合的角度进行分析，把所有的情况的共性都表现出来，可以使用动态规划

时间复杂度 $O(n^2)$

Java 代码

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length();
        int m = s2.length();
        if(s3.length() != n + m) return false;

        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;

        boolean[][] f = new boolean[n + 10][m + 10];
        for(int i = 0;i <= n;i ++)
            for(int j = 0;j <= m;j ++)
            {
                if(i == 0 && j == 0) f[i][j] = true;
                else
                {
                    if(i != 0 && s1.charAt(i) == s3.charAt(i + j)) f[i][j] |= f[i - 1][j];
                    if(j != 0 && s2.charAt(j) == s3.charAt(i + j)) f[i][j] |= f[i][j - 1];
                }
            }
        return f[n][m];
    }
}