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