作者bleed1979 (十三)
站内Prob_Solve
标题Re: [问题] Google Interview Question (1)
时间Mon Feb 11 14:14:23 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?
还没很仔细想，粗浅的以为 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)
1F：→ bleed1979:懒得在改了，应该是YES vs. NO TRUE vs. FALSE 02/11 14:22
2F：→ atoi:A:"acd" B:"bac" C:"bacadc" ?? 02/11 14:28
3F：→ bleed1979:interleave是插入，不能改变顺序吧。我以为cd != dc 02/11 14:30
4F：推 stimim:可以分成 b##a#c 和 #ac#d# 02/11 14:31
5F：→ bleed1979:我了了，在想想。 02/11 14:32