Leetcode: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：

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

示例 2：

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

示例 3：

输入：s1 = "", s2 = "", s3 = ""输出：true

提示：

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• s1、s2、和s3都由小写英文字母组成

进阶：您能否仅使用O(s2.length)额外的内存空间来解决它?

还是直接上代码，特别简单的动态规划：

class Solution { /**近乎白送分的题，一看就是动态规划，但是可能稍微复杂一点点的：三维的吗？ 三维也不是不能解，就是做起来比较麻烦，我们用二维来替代:既然s3的某个长度可以用s1的某个 长度和s2的某个长度拼出，那这段里s3的长度肯定等于s1和s2之和 */ public boolean isInterleave(String s1, String s2, String s3) { /**先转成字符数组方便操作 */ char[] sArr1 = s1.toCharArray(); char[] sArr2 = s2.toCharArray(); char[] sArr3 = s3.toCharArray(); int m = sArr1.length; int n = sArr2.length; int o = sArr3.length; if(m == 0 && n == 0 && o == 0) { return true; } if(m + n != o) { return false; } /**dp[i][j]表示s1的前i个字符和s2的前j个字符是否可以拼出s3的前i+j个字符*/ boolean[][] dp = new boolean[m+1][n+1]; /**s1的前0个字符和s2的前0个字符肯定能拼出s3的前0个字符*/ dp[0][0] = true; /**初始化第一行和第一列，第一列是s1的前i个字符和s3的前i个字符是否相等*/ for(int i = 1; i <= m ;i++) { dp[i][0] = dp[i - 1][0] && sArr1[i - 1] == sArr3[i-1]; } /**第一列是s2的前j个字符和s3的前j个字符是否相等 */ for(int j = 1; j <= n; j++) { dp[0][j] = dp[0][j - 1] && sArr2[j - 1] == sArr3[j - 1]; } /**考虑一般的位置*/ for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { dp[i][j] = (dp[i-1][j] && sArr1[i - 1] == sArr3[i + j - 1]) || (dp[i][j - 1] && sArr2[j - 1] == sArr3[i + j - 1]); } } /**要求的是s1的整个和s2的整个能否拼出s3的整个 */ return dp[m][n]; } }