※ 引述《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;
}