Re: [問題] Google Interview Question (1)
看板Prob_Solve (計算數學 Problem Solving)作者keeperkai (keeperkai)時間11年前 (2013/04/21 20:11)推噓4(4推 0噓 6→)留言10則, 2人參與討論串12/16 (看更多)
一樣用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
推
04/21 20:57, , 1F
04/21 20:57, 1F
→
04/21 20:58, , 2F
04/21 20:58, 2F
→
04/21 20:59, , 3F
04/21 20:59, 3F
推
04/21 21:03, , 4F
04/21 21:03, 4F
→
04/21 21:11, , 5F
04/21 21:11, 5F
→
04/21 21:12, , 6F
04/21 21:12, 6F
推
04/21 21:16, , 7F
04/21 21:16, 7F
推
04/21 21:20, , 8F
04/21 21:20, 8F
→
04/21 21:21, , 9F
04/21 21:21, 9F
→
04/21 21:22, , 10F
04/21 21:22, 10F
討論串 (同標題文章)
完整討論串 (本文為第 12 之 16 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
