※ 引述《RockLee (Now of all times)》之铭言：
: 原始网址:
: http://www.careercup.com/question?id=14539805
: 题目:
: Three strings say A, B, C are given to you.
: Check weather 3rd string is interleaved from string A and B.
: Ex: A="abcd" B="xyz" C="axybczd". answer is yes. o(n)
: 用 Dynamic Programming 应该可在 O(n^2) 的时间内解决
: 但要在 O(n) 的时间内解决就想不出来了 Orz...
: CareerCup 上的讨论看来都无法在 O(n) 的时间内正确的解决
: 不知道板上有没有人有什么 idea?
也许是这样？
bool interleaved(char* A, char* B, char* C) {
int a = 0, b = 0, c = 0;
int da = 0, db = 0, dc = 0;
while (C[c])
if (A[a+da] != C[c+dc] && B[b+db] != C[c+dc])
return false;
else if (A[a+da] == C[c+dc] && B[b+db] != C[c+dc])
a += da + 1, c += dc + 1, da = db = dc = 0;
else if (A[a+da] != C[c+dc] && B[b+db] == C[c+dc])
b += db + 1, c += dc + 1, da = db = dc = 0;
else if (A[a+da] == C[c+dc] && B[b+db] == C[c+dc])
++da, ++db, ++dc;
return da == 0 && db == 0 && dc == 0;
}
大体上就跟 atoi 板友说的方法一样
至于 tkcn 板友的疑问，我的解决方法是这样：
当 C 同时出现 A 与 B 的字符时
那就继续偷看下一个字符，直到 A 与 B 的字符与 C 不一样为止
这样对吗？