題目
描述
比較兩個(gè)字符串A和B，確定A中是否包含B中所有的字符。字符串A和B中的字符都是大寫字母
樣例
給出 A = "ABCD" B = "ACD"欢际，返回 true
給出 A = "ABCD" B = "AABC"冗疮， 返回 false
解答
思路1
- 將字符串轉(zhuǎn)換成StringBuffer，按字符兩次循環(huán)比較寸宵，A中存在B的字符設(shè)置為空
- 不能用deleteChar因?yàn)閯h除字符之后StringBuffer的長(zhǎng)度就變化了
- 既然是需要全部存在崖面。內(nèi)存循環(huán)找到后break;內(nèi)層循環(huán)每次檢查之后如果有任何一個(gè)字符不存在直接返回false，如果程序走到最后還沒(méi)return fasle,return true即可梯影。
- 整體時(shí)間復(fù)雜度為O(n^2)巫员，既然題目中說(shuō)都是大寫字符，應(yīng)該能在這里做文章甲棍，得到更快的算法简识。
代碼1
public class Solution {
/**
* @param A : A string includes Upper Case letters
* @param B : A string includes Upper Case letter
* @return : if string A contains all of the characters in B return true else return false
*/
public boolean compareStrings(String A, String B) {
// write your code here
StringBuffer sb1 = new StringBuffer(A);
StringBuffer sb2 = new StringBuffer(B);
int result = 0;
for(int i = 0; i < sb2.length(); i++){
boolean temp = true;
for(int j=0; j < sb1.length(); j++){
if(sb1.charAt(j) == sb2.charAt(i)){
sb1.setCharAt(j,' ');
temp=false;
break;
}
}
if(temp) return false;
}
return true;
}
}
思路2
- 既然都是大寫字母，那么只有26種字符可能。
- 字符取值范圍確定七扰，就可以用空間復(fù)雜度換取時(shí)間復(fù)雜度奢赂。
代碼2
public class Solution {
/**
* @param A : A string includes Upper Case letters
* @param B : A string includes Upper Case letter
* @return : if string A contains all of the characters in B return true else return false
*/
public boolean compareStrings(String A, String B) {
// write your code here
StringBuffer sbA = new StringBuffer(A);
StringBuffer sbB = new StringBuffer(B);
int[] sa = new int[27];
for(int i=0; i < sbA.length(); i++){
sa[sbA.charAt(i)-'A']++;
}for(int j=0;j < sbB.length(); j++){
sa[sbB.charAt(j)-'A']--;
}
for(int k=0; k<27; k++){
if(sa[k]<0) return false;
}
return true;
}
}
