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

Question

给出三个字符串A,B和C.写一个函数,检查C是否是A和B的交织.如果C包含A和B的所有字符以及个别中所有字符的顺序,则称其为交错A和B.字符串被保留.

例如:

• 'hotdog'是'hot'和'dog'的交错(简单)
• 'superb'是'up'和'serb'的交错
• '心痛'是'耳朵'和'疼痛'的交错
• 'chat'是'hat'和'cat'的交错
• '骗子' 不是 '聊天'和'先见'的交错,因为虽然它包含了每个人的所有字母,但'先知'中的字母并没有按顺序出现

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

我的Algo:

1. 穿越a和c.在遍历时,我们首先计算两件事:char是否存在并保存索引,即f找到char的位置.一旦我们找到了char,我们应该在那个地方添加一些特殊的char,这样我们就不会再考虑这个char了.
2. 对于您在索引中a搜索的下一个char c,您在其中找到了前一个char即f.如果我们找不到回报.
3. 你也b一样.
4. 如果执行上述步骤,如果我们发现后false不是重复了第一b比a并返回结果.

例如

a = xxy, b = xxz and c = xxzxxxy

从一开始:

1. 对于x中的x,c = 0xzxxxy(我将0作为特殊字符)
2. 对于x中的x,从索引0开始(因为我们在0处找到了前一个char)c = 00zxxxy.
3. 对于y中的y,c = 00zxxx0
4. 对于b中的x,c = 00z0xx0
5. 对于b中的x,c = 00z00x0
6. 对于b中的z,我们在索引4之后找不到z,索引4是我们找到b的前一个char的索引.

因为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. 对于y中的y,c = 00000x0

因此,真正的iec是a和b的交错字符串.

Answer 1

你的解决方案代表了一个稍微修改的贪婪算法,因为它一旦找到匹配就会计算第一遍(或第二遍)上C属于的字符.这将打破以下字符串:AB

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);
}

在ideone上演示.