检查字符串C是否是由字符串A和B交错组成的。

Question

给定三个字符串A、B和C。编写一个函数，检查C是否是A和B的交错。如果C包含A和B的所有字符，并且每个字符串中所有字符的顺序都被保留，则称C为A和B的交错。

例如： - 'hotdog' 是 'hot' 和 'dog' 的交错（简单） - 'superb' 是 'up' 和 'serb' 的交错 - 'heartache' 是 'ear' 和 'ache' 的交错 - 'chat' 是 'hat' 和 'cat' 的交错 - 'cheaters' 不是 'chat' 和 'seer' 的交错，因为虽然它包含每个字符串的所有字母，但来自 'seer' 的字母没有按顺序出现

我在net中找到了一些解决方案，但下面是我的方法，有人能告诉我是否遗漏了什么或者我的算法是否可行吗？谢谢。 我的算法： Traverse through a and c. While traversal we calculate two things first: whether the char is present or not and save the index i.e. f where the char is found. And as soon as we find the char we should put some special char in that place, so that we will not consider this char further.

For the next char in a search in the c from the index where you have found the previous char i.e. f. if we don't find than return.

Same you do for b as well.

If after doing the above step if we find false than repeat for first b than a and return the result.

e.g.

a = xxy, b = xxz and c = xxzxxxy

从 a 开始：

1. 对于 a 中的每个 x，c = 0xzxxxy（我将 0 视为特殊字符）。
2. 对于 a 中的每个 x，从索引 0 开始（因为我们在索引 0 处找到了前一个字符），c = 00zxxxy。
3. 对于 a 中的每个 y，c = 00zxxx0。
4. 对于 b 中的每个 x，c = 00z0xx0。
5. 对于 b 中的每个 x，c = 00z00x0。
6. 对于 b 中的每个 z，在我们找到 b 的前一个字符的索引 4 之后，我们找不到 z。

由于以 b 开头返回 false，所以现在我们将以 b 开始。

所以从 b 开始：

1. 对于 b 中的每个 x，c = 0xzxxxy。
2. 对于 b 中的每个 x，c = 00zxxxy。
3. 对于 b 中的每个 z，c = 000xxxy。
4. 对于 a 中的每个 x，c = 0000xxy。
5. 对于 a 中的每个 x，c = 00000xy。
6. 对于 a 中的每个 y，c = 00000x0。

因此，真正的即c是a和b的交错字符串。

- Trying

---

我怀疑这个问题比起一开始听起来要复杂得多，因为你很容易走错路，不得不后退。 - Hot Licks

这个可以尽可能地花费时间吗？还是你必须满足复杂度要求？ - Cruncher

@nhahtdh，你想让我恢复它吗？我想在这里尝试新的解决方案。 - Trying

@Trying：这样可以节省大家关于你所研究的时间。我真的怀疑是否可能做得更好。 - nhahtdh

@nhahtdh 命令已执行，链接已恢复 :)。 - Trying

Answer 1

您的解决方案代表了一个带有轻微修改的贪心算法，因为在第一遍（或第二遍）找到匹配时，它会将C中的字符视为属于A（或B），这将导致以下字符串无法正常工作：

A = xxyxxy
B = xxzxxz
C = xxzxxyxxyxxz

第一个将匹配字符视为 A 成员的传递将使 C 变为。

00zxx0000xxz

第二次遍历将匹配的字符视为 B 的成员，这将把 C 转换成

00000yxxyxx0

这是一个简单的Java实现记忆化解决方案：

private static boolean checkOverlap(String a, String b, String c) {
    Boolean[][][] memoize = new Boolean[a.length()+1][b.length()+1][c.length()+1];
    return checkOverlap(a, b, c, 0, 0, 0, memoize);
}
private static boolean checkOverlap(
    String a
,   String b
,   String c
,   int pa
,   int pb
,   int pc
,   Boolean[][][] memoize
) {
    Boolean res = memoize[pa][pb][pc];
    if (res != null) {
        return (boolean)res;
    }
    if (pa == a.length() && pb == b.length() && pc == c.length()) {
        res = true;
    } else if (pc == c.length()) {
        res = false;
    } else {
        res = false;
        if (pa != a.length() && c.charAt(pc) == a.charAt(pa) && checkOverlap(a, b, c, pa+1, pb, pc+1, memoize)) {
            res = true;
        } else if (pb != b.length() && c.charAt(pc) == b.charAt(pb) && checkOverlap(a, b, c, pa, pb+1, pc+1, memoize)) {
            res = true;
        }
    }
    return (memoize[pa][pb][pc] = res);
}

在ideone上的演示。

- Sergey Kalinichenko

---

请问您能否推荐一种可能比较高效的编程方法呢？谢谢。 - Trying

尝试基于DP的解决方案（第二个）[从您在修改之前引用的网站]（http://www.geeksforgeeks.org/check-whether-a-given-string-is-an-interleaving-of-two-other-given-strings-set-2/）非常高效。您还可以通过应用[memoization](http://en.wikipedia.org/wiki/Memoization)将第一个解决方案（递归方式）转换为有效的解决方案。 - Sergey Kalinichenko

我跟着链接走了，但是在递归方法中我找不到重叠子问题，以便我可以使用记忆化。请帮我至少找到子问题，然后我就可以开始了。谢谢。 - Trying

@Trying 我添加了一个Java实现的记忆化递归解决方案，来看一下。 - Sergey Kalinichenko

@Trying 我认为我们可以，但我很难证明它。 - Sergey Kalinichenko

Answer 2

首先，我会检查A的长度和B的长度之和是否等于C的长度。

接下来，检查A的第一个字符是否等于C的第一个字符。

如果不是，则检查B的第一个字符是否等于C的第一个字符。

根据上述两个条件中哪个为真，检查以A或B开头的其他字符。

这里有一个可以进行测试的方法：

public boolean isInterleaved(String a, String b, String c) {
    int aIndex = 0;
    int bIndex = 0;
    int cIndex = 0;
    while (cIndex < c.length()) {
        if (aIndex < a.length()) {
            if (a.charAt(aIndex) != c.charAt(cIndex)) { return false; }
            cIndex++;
            aIndex++;
        }
        if (bIndex < b.length()) { 
            if (b.charAt(bIndex) != c.charAt(cIndex)) { return false; }
            cIndex++;
            bIndex++;
        }
    }

    return true;
}

你最多会调用这个方法两次。调用可能是以下两种情况之一：

if (isInterleaved(a, b, c))

或者

if (isInterleaved(b, a, c))

如果A的第一个字符和B的第一个字符相等，则检查从上一步没有开始的A或B字符串开始的其他字符。

这样，您可以为可能满足条件的字符串保存复杂的测试。

- Gilbert Le Blanc

---

谢谢您的评论。我可以进行以上所有优化，但是您能否告诉我我的上述方法是否会给我正确的结果？谢谢。 - Trying

@尝试中：我会简单地循环遍历C字符。请查看我的编辑后答案。 - Gilbert Le Blanc

我在 isInterleaved("xxxy", "xx", "xxxxxy") 中得到了索引越界的错误，并且对于 isInterleaved("x", "xx", "x") 它返回了 true。 - nhahtdh

@Trying：我忘记了A和B字符串可能长度不同。请看我的编辑后的答案。在调用此方法之前，您还应该执行我概述的其他测试。 - Gilbert Le Blanc

检查以下程序相关的内容：String A = "xxyxxy"; String B = "xxzxxz"; String C = "xxzxxyxxyxxz"; 答案应该是true，但你的代码会返回false。 - Trying

Answer 3

def isinterleave(a, b, c):
   la = len(a)
   lb = len(b)
   lc = len(c)
   if la + lb != lc: return False
   if la == lb == lc == 0: return True
   if (la > 0 and lb >0 and a[0] == b[0] == c[0]):
     return isinterleave(a[1:], b, c[1:]) or isinterleave(a, b[1:], c[1:])
   if (la > 0 and a[0] == c[0]):
     return isinterleave(a[1:], b, c[1:])
   if (lb > 0 and b[0] == c[0]):
     return isinterleave(a, b[1:], c[1:])
   return False

- MK.