[問題] Google Interview Question (1)

[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?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 111.252.71.8
推 atoi:是不是類似兩個已排序的陣列要合併成一個排序好的陣列那樣跑?
→ atoi:ㄟ好像不太正確，歹勢!!
→ tkcn:↑不行，當 A, B, C 都是同個字元開頭時，會不知該消耗哪個
→ tjjh89017:用regex去跑(誤
→ bleed1979:CareerCup在那啊？我想看一下別人的討論。
→ RockLee:↑就我附的網址
推 yoco315:無論如何只能想到 n^2   orz