※ 引述《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?
我用一个很蠢的方法试试看XD
我没有很谨慎地思考所以正确率应该是很低啦
我的想法适用regex去跑
如果
A = 'aa' B = 'abaab' C = 'aabaaab'
reA = '\w*a\w+a\w*'
reB = '\w*a\w+b\w+a\w+a\w+b\w*'
然后去run看看C有没有都符合
这样应该能简单去除几个结果，剩下比较刁钻的应该就没办法了
那如果这样有没有办法能就改进呢?
请版大们赐教<(_ _)>