作者pnpncat (meow)
站內Prob_Solve
標題Re: [問題] Google Interview Question (1)
時間Fri Mar 29 16:49:15 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?
這題不能直接這樣做嗎？
1. 將A, B, C分別放進stackA, stackB, stackC
2. 以下列函數判別答案是否為真
bool foo() {
while ( stackC is not empty ) {
if ( top of stackC == top of stackA ) {
pop stackC;
pop stackA;
} else if (top of stackC == top of stackB ) {
pop stackC;
pop stackB;
} else {
return false;
}
}
return true;
}
--
直接閱讀《琴劍六記》
http://gs.cathargraph.com/p/list.html
《琴劍六記》Facebook專頁
https://www.facebook.com/GSannals
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.176.10.104
1F：→ flere:當top stack of C跟top A,B一樣的時候,無法判斷pop哪一個 03/29 18:05
2F：→ flere:stack才會是正確的~ 03/29 18:05
3F：→ pnpncat:咦@@ 是這樣嗎? 不是隨便pop哪一個都一樣嗎? 我把code裡 03/29 21:12
4F：→ pnpncat:面的A B對調 應該還是會得到同樣的結果吧 03/29 21:13
5F：→ flere:A=ab,B=ac,C=acab,你看到第一個a的時候,如果popA的a的話 03/29 21:21
6F：→ flere:等等看到c就會找不到對應的了(還是我誤會了嗎??XDD 03/29 21:21
7F：→ pnpncat:瞭解了^^" 03/29 21:21
8F：→ pnpncat:是我想錯XD 03/29 21:22
9F：→ pnpncat:等等 不對啊 這樣等下會找到c啊........... 03/29 21:23
10F：→ pnpncat:那時候c就在stackB上面不是嗎? 03/29 21:24
11F：→ pnpncat:我剛重想了一下 這算法應該是沒錯的 就跟沒有蓋牌的接龍 03/29 21:25
12F：→ pnpncat:道理一樣 不可能會接不起來吧 03/29 21:25
13F：→ flere:可是這時候stackB最上面會是a耶,如果你說最上面會是c的話, 03/29 22:03
14F：→ flere:那我改成A=ba,B=ca,C=baca 03/29 22:04
15F：→ flere:因為pop a同時有兩個stack符合,所以會不確定pop哪個stack才 03/29 22:05
16F：→ flere:對~ 03/29 22:05
17F：→ pnpncat:確實耶@@ 雖然直接用A往下搜到完也能解 但就不是O(n)了... 03/29 23:46
18F：→ pnpncat:看來還是要多用一個容器 把沒有match的依序存起來才行 03/29 23:54
我多加一個空的queue做做看
bool foo() {
while (stackC is not empty) {
if (top of stackC == top of stackA) {
pop stackC;
pop stackA;
} else {
enqueue(top of stackC);
pop stackC;
}
}
if (stackA is not empty) return false;
while (queue is not empty) {
if (head of queue == top of stackB) {
dequeue;
pop stackB;
} else {
return false;
}
}
return true;
}
這樣就還是 O(n)......... 這次有想錯嗎??
※ 編輯: pnpncat 來自: 180.176.10.104 (03/30 00:14)
19F：推 ledia:"accc", "bcbc", "abcccbcc" 03/31 02:12
20F：→ pnpncat:看來是我把它想得太簡單了@@ 03/31 22:54