Java 中的交错字符串问题

这是谷歌、亚马逊、TCS、Accenture、Adobe、Apple、Infosys、Microsoft、Yahoo 等顶级 IT 公司面试中经常出现的非常有趣的问题。通过解决这个问题，人们希望检查应聘者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将讨论**什么是交错字符串**以及**如何检查给定字符串是否是交错字符串**。我们还将使用不同的方法和逻辑创建 Java 程序。

什么是交错字符串？

如果字符串 Str3 包含 Str1 和 Str2 的所有字符，则称 Str3 是 Str1 和 Str2 的交错字符串。请记住，单个字符串中所有字符的顺序都得以保留。

示例

输入： Str1 = "aabcc", Str2 = "sbbca" 和 Str3 = "aasbbcbcac"

输出：字符串 3 是交错字符串。

解释： "aa"（来自 Str1）+ "sbbc"（来自 Str2）+ "bc"（来自 Str1）+ "a"（来自 Str2）+ "c"（来自 Str1）

让我们看另一个例子。

输入： Str1 = "ttbhh", Str2 = "kbbht", Str3 = "ttkbbbthhh"

输出：字符串 3 不是交错字符串。

解释：无法通过交错 Str1 和 Str2 来获取 Str3。

问题陈述

在此问题中，我们给出了三个字符串 Str1、Str2 和 Str3，编写一个程序来检查 Str3 是否是 Str1 和 Str2 的交错。

问题解决方案

可以使用以下三种方法解决此问题

• 暴力破解法
• 使用二维动态规划
• 使用一维动态规划

暴力破解法

在此方法中，我们必须注意以下两点：

• 如果 Str3 的第一个字符与 Str1 的第一个字符匹配，我们则将 Str1 和 Str3 中的下一个字符向前移动，并递归调用函数。
• 如果 Str3 的第一个字符与 Str2 的第一个字符匹配，我们则将 Str2 和 Str3 中的下一个字符向前移动，并递归调用函数。

解决问题的步骤

1. 首先，我们检查基本情况。如果 Str1、Str2 和 Str3 都**为空**，则返回 **true**，因为空 Str3 是 Str1 和 Str2 的交错。
2. 再次，检查 Str3 是否为空，而 Str1 和 Str2 中至少有一个不为空，则返回 **false**。这意味着 length(Str3) 小于 **length(Str1) + length(Str2)**。
3. 如果上述两种情况都不匹配，则继续处理以下两种情况：
   1. 如果 **Str3[0] == Str1[0]**，则检查 **Str1[1…], Str2, Str3[1…]**
   2. 如果 **Str3[0] == Str2[0]**，则检查 **Str1, Str2[1…], Str3[1…]**
   3. 如果上述两种可能性中的任何一种为真，则返回 **true**，否则返回 false。

让我们用一个函数来实现上述方法。

复杂度

上述方法的时间复杂度为 **O(n²)**，因为 Str3 的每个字符可能有两种选择。空间复杂度为 **O(1)**，因为在此方法中我们没有考虑递归堆栈空间。

使用二维动态规划

在此方法中，我们将构建一个二维 DP 表，根据下面显示的绘制路径。此处必须保持一定的顺序，以便我们能够向右或向下移动以创建有效路径。这就是 DP[i][j] 依赖于 DP[i - 1][j] 和 DP[i][j - 1] 的原因。

为了获得 DP[i][j]，请在上面显示的 DP 表中存储 true 或 false。此处，DP[i][j] 表示 str3.substr(0, i+j) 可以由 str1.substr(0, i) 与 str2.substr(0, j) 交错形成。

让我们看看该方法的实现。

首先，创建一个名为 DP[] 的二维布尔数组。在此数组中，DP[i][j] 表示是否可以获得长度为 (i+j+2) 的子字符串。它是 Str3 的前缀，通过交错长度分别为 (i+1) 和 (j+1) 的字符串 Str1 和 Str2 的前缀来获得。

简而言之，DP 表表示当 S1 在 i-th 索引处，S2 在 j-th 索引处时，str3 是否在 (i+j)-th 索引处交错。0th 索引表示空字符串。0th 索引表示空字符串。我们可以得出结论：

• 如果 **str1** 和 **str2** 为空，则 **str3** 也将**为空**。因此，我们可以认为它是**交错的**。
• 如果只有 **str1** 是空字符串，并且如果前一个 **str2** 位置是交错的，并且当前的 **str2** 位置字符等于 **str3** 当前位置字符，则它将被视为**交错的**。
• 如果 str2 为空，则情况相同。当 str1 和 str2 都不为空时，每当我们从 i-1, j 到达 i, j 时，如果 i-1, j 已经是交错的，并且 i 和当前的 str3 位置相同，那么它们就是**交错字符串**。如果我们从 i, j-1 到达 i, j，并且如果 i, j-1 已经是交错的，并且 j 和当前的 str3 位置相同，那么它也是**交错的**。

解决问题的步骤

• 创建一个大小为 m+1 和 n+1 的二维布尔 DP[] 数组。其中 m 和 n 分别是 Str1 和 Str2 的长度。
• 现在根据相应地比较 Str1、Str2 与 Str3 的字符来填充 DP 表。
• 返回 DP[m][n]

InterleavingStringExample2.java

输出

true

复杂度

上述方法的**时间和空间复杂度为 O(m\*n)**，其中 m 和 n 是字符串的长度。

使用一维动态规划

该方法与上述方法相同。唯一不同的是，我们只使用了一维数组来存储我们进一步处理的指定字符串前缀的结果。使用一维数组的优点是我们只需要在需要时使用 dp[i-1] 和 dp[i] 的先前值来更新数组的元素 dp[i]。

让我们在 Java 程序中实现上述方法。

InterleavingStringExample3.java

输出

true

复杂度分析

上述方法的**时间复杂度为 O(m\*n)**，因为大小为 m\*n 的 dp[] 数组被填充了 mn 次。**空间复杂度为 O(n)**，其中 n 是字符串 str1 的长度。