Re: [問題] Google Interview Question (1)
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/02/11 13:33)推噓1(1推 0噓 2→)留言3則, 2人參與討論串2/16 (看更多)
※ 引述《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?
這是一個很快的想法, 我不知道對不對,
反正大家討論一下.
You can put two flags on string A and B,
then scan every character in C.
for example, the first step,
it will be, A = a | bcd and B = | xyz.
then it's not hard to see if the flag of A,B move to the end.
One problem is the one it points out in the webpage.
if A = 'ca', B = 'cb' , C = 'cacb' or 'cbca' should be both true.
So, when you scan the character, you need to put an additional index
to handle the duplicate character.
In this situation, C = 'cacb', when you do the scan of the fist char
A = c | a and B = c | b, but both has index = 1.
In the next step, you scan second char, which is a,
Now, A = 'c a |' and you reset the index of A into 0.
at the same time you push the flag of B back with 1.
So B = '| c b'.
This should be running in a linear time?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 142.136.127.217
推
02/11 14:02, , 1F
02/11 14:02, 1F
→
02/11 16:35, , 2F
02/11 16:35, 2F
→
02/11 16:40, , 3F
02/11 16:40, 3F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
