※ 引述《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?
这题不能直接这样做吗？
1. 将A, B, C分别放进stackA, stackB, stackC
2. 以下列函数判别答案是否为真
bool foo() {
while ( stackC is not empty ) {
if ( top of stackC == top of stackA ) {
pop stackC;
pop stackA;
} else if (top of stackC == top of stackB ) {
pop stackC;
pop stackB;
} else {
return false;
}
}
return true;
}