java - 检查字符串 C 是否是 A 和 B 的交错

Question

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

例如:

• “hotdog”是“hot”和“dog”的交错(简单)
• “superb”是“up”和“serb”的交错
• “心痛”是“耳朵”和“疼痛”的交错
• “聊天”是“帽子”和“猫”的交错
• 'cheaters' 不是 'chat' 和 'seer' 的交错，因为虽然它包含每个字母的所有字母，但 'seer' 的字母没有按顺序出现

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

我的算法:

1. 遍历a和c。在遍历时，我们首先计算两件事:char 是否存在并保存索引，即找到 char 的 f。一旦我们找到该字符，我们就应该在那个地方放置一些特殊的字符，这样我们就不会进一步考虑这个字符。
2. 对于 a 中的下一个字符，在 c 中从您找到前一个字符的索引处搜索，即 f。如果找不到就返回。
3. 您也为 b 做同样的事情。
4. 如果在执行上述步骤后，如果我们发现 false 则重复第一个 b 而不是 a 并返回结果。

例如

a = xxy, b = xxz and c = xxzxxxy

start with a:

1. for x in a, c = 0xzxxxy (i am putting 0 as special char)
2. for x in a, start from the index 0 onwards(because we have found the previous char at 0)c = 00zxxxy.
3. for y in a, c = 00zxxx0
4. for x in b, c = 00z0xx0
5. for x in b, c = 00z00x0
6. for z in b, we could not find z after the index 4 which was the index where we found the previous char for b.

as starting with a returns false so we will start with b now.

So start with b:

1. for x in b, c = 0xzxxxy
2. for x in b, c = 00zxxxy
3. for z in b, c = 000xxxy
4. for x in a, c = 0000xxy
5. for x in a, c = 00000xy
6. for y in a, c = 00000x0

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

Answer 1

您的解决方案代表一个 greedy algorithm稍作修改，因为它在第一遍中将 C 中的字符计为属于 A(或在第二遍中属于 B)一旦找到匹配项。这将中断以下字符串:

A = xxyxxy
B = xxzxxz
C = xxzxxyxxyxxz

将匹配字符计为 A 成员的第一遍将把 C 变成

00zxx0000xxz

将匹配字符计为 B 成员的第二遍将把 C 变成

00000yxxyxx0

这是 memoized 的简单 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);
}

Demo on ideone.