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