作者keeperkai (keeperkai)
看板Prob_Solve
标题Re: [问题] Google Interview Question (1)
时间Sun Apr 21 20:11:14 2013
一样用flagA=0, flagB=0开始
flagC = 0代表目前在C里面验证的字元位置,令A[],B[],C[]为分别三个string
基本精神为,从flagC开始一一把C往後分别跟A,B的字串进行比对，分别把与C相同的字元数存入sameLengthA sameLengthB，如果:
1.sameLengthA, sameLengthB有任何一者比较长 那就代表此段取sameLength长度较长字串的片段(因为如果取较短的一定错), Ex:
sameLengthA=1,sameLengthB=3就把flagC+=sameLengthB, flagB+=sameLengthB
2.sameLengthA, sameLengthB相同:
出现这种状况 只有以下两种可能:
(i)flagA+sameLengthA+1==A字串长度或者flagB+sameLengthB=B字串长度 简单来说 就是其中一者已经读到尾巴了
(ii)C不是A,B交错而成，原因如下:
因为(i)已经排除了AB读完的状况 所以AB後面必有字元
如果A[flagA+sameLengthA+1]=/=B[flagB+sameLengthB+1]
则代表不管是A[flagA+sameLengthA+1]还是B[flagB+sameLengthB+1]都不是C[flagC+sameLengthA+1] 所以C不是AB交错而成
如果A[flagA+sameLengthA+1]==B[flagB+sameLengthB+1]
则代表A[flagA+sameLengthA+1]==B[flagB+sameLengthB+1]都不等於C[flagC+sameLengthA+1] 所以C不是AB交错而成
implementation:
bool checkinterleave(char A[],char B[], char C[]){//returns true when C is interleaved by A,b;else return false
int flagA;int flagB;int flagC;
int tA;int tB; int tC;
int sameLengthA;int sameLengthB;
tA=tB=tC=flagA=flagB=flagC=0;
int lenA=strlen(&A[0]);int lenB=strlen(&B[0]);int lenC=strlen(&C[0]);
while(flagC<lenC){
//find sameLengthA
sameLengthA=0;
tA=flagA;
tC=flagC;
while((tA<lenA)&&(A[tA]==C[tC])){
sameLengthA++;
tA++;
tC++;
}
//find sameLengthB
sameLengthB=0;
tB=flagB;
tC=flagC;
while((tB<lenB)&&(A[tB]==C[tC])){
sameLengthB++;
tB++;
tC++;
}
if(sameLengthA==sameLengthB){
return false;
}else{
if(sameLengthA>sameLengthB){
flagC+=sameLengthA;
flagB+=sameLengthB;
}else{
flagC+=sameLengthA;
flagA+=sameLengthA;
}
if((flagC==lenC)&&(flagB==lenB)&&(flagA==lenC)){
return true;
}
}
}
}
不知道这样行不行?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 182.155.18.227
1F：推 LPH66:先不论对错, 你这是 O(n^2) 吧... 04/21 20:57
2F：→ LPH66:再者 A = B = "abc" C = "abcabc" 好像是反例 04/21 20:58
3F：→ LPH66:或者如果你觉得这个 C 太扯 那 "abacbc" 也可以 04/21 20:59
4F：推 LPH66:唔, 实际跑你这段程式, 最简单的 abc def adbecf 就炸了 XD 04/21 21:03
5F：→ keeperkai:我不懂为什麽会是O(n^2)? C的每个字元只针对A,B个比对一 04/21 21:11
6F：→ keeperkai:一次 之後是直接加上去 04/21 21:12
7F：推 LPH66:嗯, 仔细想想後应该是线性没错, 不过正确性就... 04/21 21:16
8F：推 LPH66:ok, 这程式码里有些打错字的地方, 但即使修过後 04/21 21:20
9F：→ LPH66:abc abc abcabc 跟 abc abc abacbc 都回传 false 04/21 21:21
10F：→ LPH66:更夸张一点的例包含 aaa aaa aaaaaa 也是你的演算法的反例 04/21 21:22