這是近幾天在LintCode上遇到的一道題，題目如下：
比較兩個(gè)字符串A和B面殖，確定A中是否包含B中所有的字符。字符串A和B中的字符都是大寫字母:
給出 A = "ABCD" B = "AABC"， 返回 false
給出 A = "ABCD" B = "ACD"透揣，返回 true
- 一開始的思路是用A的每一位去和B的每一位去比較婴渡。
如果說B每一位都能在A中找到的話幻锁，則A中包含B。
代碼如下：
bool compareStrings(string A, string B) {
int countA = A.length();
int countB = B.length();
int sub = 0;
int temp[countB];
for (int i = 0; i < countB; i++) {
temp[i]=0;
}
for (int i = 0; i < countA; i++) {
for (int n = 0; n < countB; n++) {
if ( A[i] == B[n]) {
temp[n] = 1;
}
}
}
for (int i = 0; i < countB; i++) {
sub = temp[i] + sub;
}
if (sub == countB)
return true;
else
return false;
}
但是在遇到B的字符里有A的重復(fù)個(gè)的時(shí)候：
"ABCDEFG", "ACC"
A的同一個(gè)C會(huì)在B中判斷兩次边臼，導(dǎo)致輸出的結(jié)果為true哄尔，但其實(shí)應(yīng)該為false。
-
所以這次改進(jìn)代碼柠并，避免一個(gè)字符的多次判定岭接。
要做的很簡單，在判定存在的語句后面加上一個(gè)break臼予。for (int i = 0; i < countA; i++) { for (int n = 0; n < countB; n++) { if ( A[i] == B[n]) { temp[n] = 1; break; } } }
就像上面提到的情況鸣戴，問題又出現(xiàn)了：
"AAAAAAAAAAAABBBBBCDD", "ABCDD"（true）
A的DD在B中只判定了B的第一個(gè)D，就跳出了粘拾，所以輸出為false窄锅。
-
……很無奈接著補(bǔ)充代碼：
for (int i = 0; i < countA; i++) { for (int n = 0; n < countB; n++) { if ( A[i] == B[n]) { temp[n] = 1; if ( A[i] != A[i-1])//當(dāng)A的后一個(gè)字符與前一個(gè)不一樣時(shí)才跳出循環(huán) break; } } }
好吧，糟糕的情況又出現(xiàn)了缰雇。
"AAAAAAAAAAAAAAAAAAABBBBBBBBBDFADSFJALSDJFALSDJFSADFADF", "AAAAAABBBBBBBBBDFJALDJF"（true）
這里又錯(cuò)誤的返回了一個(gè)fasle入偷，由于A中的D并不是連續(xù)，所以和上面的錯(cuò)誤類似械哟，B中的第二個(gè)D不能得到判定盯串。
做到這里就不得不說下了，像你已經(jīng)看到這種修修補(bǔ)補(bǔ)的代碼戒良，一般情況下都是很糟糕的体捏，而且問題較多。因?yàn)楸仨氁樦懊娴乃悸罚瑏斫鉀Q后面的問題 几缭，你很有可能發(fā)現(xiàn)之前的算法結(jié)構(gòu)在解決后面出現(xiàn)問題時(shí)是異常困難的河泳。最好構(gòu)造算法之前就要考慮到最壞的情況，或者說最后重構(gòu)下自己的代碼年栓。
由于我一開始看到題目中給的的數(shù)據(jù)很簡單就沒考慮到現(xiàn)在的情況拆挥。
我覺得我的方法需要換一種了。
思路如下：
- 統(tǒng)計(jì)兩邊的信息進(jìn)行比較某抓。如果B中的每種字符的個(gè)數(shù)小于等于A中的纸兔，則A包含B。
代碼如下：
int Achar[26];//儲存字符串的每個(gè)字母個(gè)數(shù)
int Bchar[26];
for (int i = 0; i<26; i++) {
Achar[i] = 0;
Bchar[i] = 0;
}
int Adate,Bdate;//記錄AB的字符統(tǒng)計(jì)數(shù)據(jù)
int countA = A.length();
int countB = B.length();
for (int i = 0; i<countA; i++) {
int index;
index = A[i] - 65;
Achar[index]++;
}
for (int i = 0; i<countB; i++) {
int index;
index = B[i] - 65;//65為大寫A的ASCⅡ碼值
Bchar[index]++;
}
for (int i = 0; i<26; i++) {
if (Achar[i]<Bchar[i])
return false;
}
return true;
}
這一次19個(gè)測試數(shù)據(jù)全部通過否副。??
