leetcode97. 交错字符串-java实现

题目所属分类

方案数的话很多 这样就成立和数量的可以考虑用DP

原题链接

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …
注意：a + b 意味着字符串 a 和 b 连接。

代码案例：
输入：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
输出：true

题解

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

可以看s3里面最后的元素属于谁 这样的分类 如果最后i+j个字符属于s1 那么就是s1的前i-1个字符 是否组成i+j-1的s3方案 也就是说f[i-1][j]

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;
        boolean[][] f = new boolean[n+10][m+10];
        s1 = " "+s1;
        s2 = " "+s2;
        s3 = " "+s3;
        
        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] || f[i][j-1];
                } 
            }
        }
        return f[n][m];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22