LeetCodeNO.97交错字符串问题解析与实现

问题描述

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

示例 1: 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2: 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

题目链接: LeetCode NO.97

解决方案

直接比较法

首先，我们可以通过直接比较的方法来解决问题。这种方法涉及逐个字符地将s3与s1和s2进行对比。当s1和s2在某个位置上的字符相同时，会产生两个可能的分支。每个分支都需要分别进行判断，以确定s3是否可以由s1和s2交错形成。

然而，这种直接的方法在处理较大字符串时效率较低。

动态规划方法

为提高效率，可以采用动态规划的方法。通过构建一个二维数组dp，其中dp[i][j]表示s1的前i个字符和s2的前j个字符能否形成s3的前i+j个字符。具体实现如下：

public class Solution2 { public static boolean isInterleave(String s1, String s2, String s3) { int l1 = s1.length(), l2 = s2.length(), l3 = s3.length(); if (l1 + l2 != l3) return false; boolean[][] dp = new boolean[l1+1][l2+1]; dp[0][0] = true; for (int i = 0; i <= l1; i++) { for (int j = 0; j <= l2; j++) { int k = i + j - 1; if (i == 0 && j == 0) continue; else if (i > 0 && j == 0) dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(k); else if (i == 0) dp[i][j] = dp[i][j-1] && s2.charAt(j-1) == s3.charAt(k); else dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(k)) || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(k)); } } return dp[l1][l2]; }

记忆化递归方法

结合上述两种方法，我们可以使用记忆化递归来进一步优化。这种方法通过记录已经计算过的状态来避免重复计算，从而提高算法的效率。具体实现如下：

public class Solution3 { static boolean[][] dp; static int l1, l2, l3; static char[] c1, c2, c3; public static boolean isInterleave(String s1, String s2, String s3) { l1 = s1.length(); l2 = s2.length(); l3 = s3.length(); if (l1 + l2 != l3) return false; c1 = s1.toCharArray(); c2 = s2.toCharArray(); c3 = s3.toCharArray(); dp = new boolean[l1+1][l2+1]; return isMatch(0, 0, 0); } private static boolean isMatch(int i, int j, int k) { if (dp[i][j] || i > l1 || j > l2) return false; if (l1 == i && l2 == j) return true; if (i