作者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