Re: [問題] Google Interview Question (1)
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間11年前 (2013/02/11 16:59)推噓0(0推 0噓 3→)留言3則, 2人參與討論串4/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?
也許是這樣？
bool interleaved(char* A, char* B, char* C) {
int a = 0, b = 0, c = 0;
int da = 0, db = 0, dc = 0;
while (C[c])
if (A[a+da] != C[c+dc] && B[b+db] != C[c+dc])
return false;
else if (A[a+da] == C[c+dc] && B[b+db] != C[c+dc])
a += da + 1, c += dc + 1, da = db = dc = 0;
else if (A[a+da] != C[c+dc] && B[b+db] == C[c+dc])
b += db + 1, c += dc + 1, da = db = dc = 0;
else if (A[a+da] == C[c+dc] && B[b+db] == C[c+dc])
++da, ++db, ++dc;
return da == 0 && db == 0 && dc == 0;
}
大體上就跟 atoi 板友說的方法一樣
至於 tkcn 板友的疑問，我的解決方法是這樣：
當 C 同時出現 A 與 B 的字元時
那就繼續偷看下一個字元，直到 A 與 B 的字元與 C 不一樣為止
這樣對嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.225.133.120
※ 編輯: DJWS 來自: 36.225.133.120 (02/11 17:00)
→
02/11 17:03, , 1F
02/11 17:03, 1F
→
02/11 17:08, , 2F
02/11 17:08, 2F
→
02/12 02:23, , 3F
02/12 02:23, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 16 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
