Leetcode--Java--97. 交错字符串

给定三个字符串 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 连接。

动态规划

1. 状态表示：
   
   f[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符是否可以交错组成 s3 的前 i + j 个字符。
2. 状态计算
   
   看s3中第 i + j个字符是属于s1还是s2。
   
   根据s3中最后一个字符等于s1还是s2，来进行状态转化
   整体非空只要左右两种方案有一种非空即可。

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
      int m = s1.length(), n = s2.length();
       //长度不同 肯定不能
      if (m + n != s3.length()) return false;
      //f[i][j]表示S1前i个字符和s2前j个字符是否能交错组成s3前i + j个字符
      boolean f[][] = new boolean[m + 1][n + 1];
      //前面补空，方便下标统一从1开始
      s1 = " " + s1;
      s2 = " " + s2;
      s3 = " " + s3;
      for (int i = 0; i <= m; i ++ ) {
          for (int j = 0; j <= n; j ++ ) {
              //s1和s2都是前0个字符串 也就是空 则整体也是空可组成
              if (i == 0 && j == 0) f[i][j] = true;
            //   如果s1最后一个字符和s3匹配  则转化为前i - 1个
              if (i > 0 && s1.charAt(i) == s3.charAt(i + j)) f[i][j] = f[i - 1][j];
            //   注意这要加 || 有可能上面的if也执行了  所以只要有一种方案可以就行
              if (j > 0 && s2.charAt(j) == s3.charAt(i + j)) f[i][j] = f[i][j] || f[i][j - 1];
          }
      }
      return f[m][n];
    }
}