Re: [問題] Google Interview Question (1)
看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間11年前 (2013/02/11 14:14)推噓1(1推 0噓 4→)留言5則, 3人參與討論串3/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?
還沒很仔細想，粗淺的以為 C - B = A 或 C - A = B
Ex. C - B = A
axybczd
xy z
a##bc#d
a bc d
worst case = O(2 * N)
使用兩次類似的程式去比
虛擬碼：
int c = 0, b = 0, a = 0;
while(c < length of C && b < length of B) {
if(C[c] == B[b]) {
++c;
++b;
C[c] = '#'; // 一定要是AB以外的字元
} else {
++c;
}
}
if(b < length of B) {
output FALSE;
} else {
c = 0, a = 0;
while(c < length of C && a < length of A) {
if(C[c] == A[a]) {
++c;
++a;
C[c] = '#';
} else {
++c;
}
}
if(a < length of A) {
output FALSE;
} else if(C is not all '#') {
output FALSE;
} else {
outout YES;
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.177.97
※ 編輯: bleed1979 來自: 114.32.177.97 (02/11 14:16)
→
02/11 14:22, , 1F
02/11 14:22, 1F
→
02/11 14:28, , 2F
02/11 14:28, 2F
→
02/11 14:30, , 3F
02/11 14:30, 3F
推
02/11 14:31, , 4F
02/11 14:31, 4F
→
02/11 14:32, , 5F
02/11 14:32, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 16 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
