作者tjjh89017 (伊達政宗)
看板Prob_Solve
標題Re: [問題] Google Interview Question (1)
時間Wed Feb 13 17:08:35 2013
※ 引述《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