※ 引述《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有没有都符合 这样应该能简单去除几个结果，剩下比较刁钻的应该就没办法了 那如果这样有没有办法能就改进呢? 请版大们赐教<(_ _)> -- 「二十年後，你会懊悔更多的是那些现在没做 而不是真的做了的事。 所以，抛开绳结，驶离安全的港湾。 掌握好你的风向 勇敢的探险，梦想，发现吧。」——马克˙吐温 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 114.41.4.179