给出三个字符串A，B和C.编写一个函数，检查C是否是A和B的交织。如果C包含A和B的所有字符以及个别中所有字符的顺序，则称其为交错A和B.字符串被保留。
例如：
- 'hotdog'是'热'和'狗'的交错（简单）
- 'superb'是'up'和'serb'的交错
- '心痛'是'耳朵'和'疼痛'的交错
- 'chat'是'hat'和'cat'的交错
- '骗子'是 不 'chat'和'seer'交错，因为虽然它包含了每个字母的所有字母，但'seer'中的字母并没有按顺序出现
我找到了一些解决方案 净 但下面是我的方法可以有人告诉我，我错过了什么或 我的算法会起作用吗？ 谢谢。
我的Algo：
- 遍历
a 和 c。在遍历时，我们首先计算两件事：char是否存在并保存索引，即 f 找到char的地方。一旦我们找到了char，我们应该在那个地方放一些特殊的char，这样我们就不会再考虑这个char了。
- 对于下一个char
a 搜索 c 从你找到以前的char的索引，即 f。如果我们找不到回报。
- 和你一样
b 同样。
- 如果我们找到以后做了上述步骤
false 而不是重复第一次 b 比 a 并返回结果。
例如
a = xxy, b = xxz and c = xxzxxxy
从一开始：
- 对于a中的x，c = 0xzxxxy（我将0作为特殊字符）
- 对于x中的x，从索引0开始（因为我们在0处找到了前一个char）c = 00zxxxy。
- 对于y中的y，c = 00zxxx0
- 对于b中的x，c = 00z0xx0
- 对于b中的x，c = 00z00x0
- 对于b中的z，我们在索引4之后找不到z，索引4是我们找到b的前一个char的索引。
从一开始 a 返回false，所以我们将开始 b 现在。
所以从b开始：
- 对于b中的x，c = 0xzxxxy
- 对于b中的x，c = 00zxxxy
- 对于b中的z，c = 000xxxy
- 对于a中的x，c = 0000xxy
- 对于a中的x，c = 00000xy
- 对于y中的y，c = 00000x0
因此，true.cs是a和b的交错字符串。
您的解决方案代表了 贪心算法 稍加修改，因为它计算了一个字符 C 属于 A 在第一关（或 B 在第二次通过时，一旦找到匹配。这会破坏以下字符串：
A = xxyxxy
B = xxzxxz
C = xxzxxyxxyxxz
第一次传递将一个匹配的角色计为一个成员 A 将转向 C 成
00zxx0000xxz
第二个传递将匹配字符计为其成员 B 将转向 C 成
00000yxxyxx0
这是一个简单的Java实现 memoized 解：
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上演示。
首先，我检查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字符串开头的其他字符。
这样，您可以保存可能满足条件的字符串的复杂测试。
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