11

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

例如：

  • 'hotdog' 是 'hot' 和 'dog' 的交错（简单）
  • “superb”是“up”和“serb”的交错
  • “heartache”是“ear”和“ache”的交错
  • “聊天”是“帽子”和“猫”的交错
  • 'cheaters'不是'chat' 和 'seer' 的交错，因为虽然它包含来自每个人的所有字母，但来自 'seer' 的字母并没有按顺序出现

我在网上找到了一些解决方案，但下面是我的方法有人可以告诉我我错过了什么或者我的算法会起作用吗？谢谢。

我的算法：

  1. 遍历a和c。在遍历时，我们首先计算两件事：char 是否存在并保存索引，即f找到 char 的位置。一旦我们找到这个字符，我们应该在那个地方放一些特殊的字符，这样我们就不会再考虑这个字符了。
  2. 对于从您找到前一个字符的索引中a搜索的下一个字符，即。如果我们没有找到比返回。cf
  3. 你也b一样。
  4. 如果在执行上述步骤后，如果我们发现falsethan 重复 first bthana并返回结果。

例如

a = xxy, b = xxz and c = xxzxxxy

从一个开始：

  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，我们在索引 4 之后找不到 z，这是我们找到 b 的前一个字符的索引。

由于从a返回 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

因此真正的iec是a和b的交错串。

4

3 回答 3

9

您的解决方案代表了一个稍作修改的贪心算法，因为一旦找到匹配项，它就会在第一遍（或第二遍）中将一个字符计C为属于。这将中断以下字符串：AB

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 上的演示。

于 2013-09-06T18:37:51.557 回答
0

首先，我会检查 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 字符串开头的其他字符。

这样，您就可以节省对可能满足条件的字符串的复杂测试。

于 2013-09-06T18:18:01.713 回答
0 
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
于 2013-09-06T19:29:17.737 回答