原始網址:
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?

是不是類似兩個已排序的陣列要合併成一個排序好的陣列那樣跑?ㄟ好像不太正確，歹勢!!

↑不行，當 A, B, C 都是同個字元開頭時，會不知該消耗哪個

用regex去跑(誤

CareerCup在那啊？我想看一下別人的討論。

↑就我附的網址

無論如何只能想到 n^2 orz