97. 交错字符串

https://leetcode.cn/problems/interleaving-string/
问题的困难点在于如何使用动态规划的方法进行更新,即子问题是啥?
这道题的难点在于有三个字符串,有三个字符串,遇到这类问题肯定不能看S1,S2,只能去看S3,根据题意,

• S3由S1和S2交错组成,那么子问题应该变为S3的部分是否可以被S1/S2的部分组成
• S1 S2交错的时候 S1内部的字符串还是有顺序的,同理 S2一样
• S3的前半部分只能S1或S2的前半部分或者S1/S2整体组成
  综上可得:
  因为是两个字符串,我们用长度n,m 表示S1.len S2.len,其中i,j表示S1,S2的部分长度,其中0<= i <= S1.len 0<= j <= S2.len,表示组成S3的i+j位
  那么F[i,j] 表示S3的前i+j位是否可以被组成,{true or false},取决于:

1. 当S3[i+j -1] == S1[i-1]时,F[i,j] = F[i-1,j]
2. 当S3[i+j -1] == S2[j-1]时,F[i,j] = F[i,j-1]
3. F[0,0] = true 相当于 S1出0个 S2出0个组成S3的0个,那么一定为true
4. F[0,j] = F[0, j-1] && S3[i+j -1] == S2[j-1]

总结:

1. (F[i,j] = F[i-1, j] && S1[i-1] == S3[i+j-1]) || (F[i,j] = F[i,j -1] && S2[j-1] == S3[i+j-1]), 条件: 0< i < S1.len & 0 < j < S2.len
2. F[0][0] = true 条件:i ==0 j == 0
3. F[0][j] = F[0][j-1] && S2[j-1] == S3[i+j-1]; 条件:i== 0; 0 < j < S2.len
4. F[i][0] = F[i-1]0] && S1[i-1] == S3[i+j-1]; 条件: 0< i < S1.len; j ==0
   同步注意 输入的边界条件:
   S1 S2 S3可能为空

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

问题1:没有计算好数组的长度

image.png

问题2:没有边界条件 当S1/S2/S3都为空的时候

image.png

问题3: F存储数据的位置和真实字符串的问题相互转换

image.png