LintCode-55.比较字符串
题目
描述
比较两个字符串A和B，确定A中是否包含B中所有的字符。字符串A和B中的字符都是大写字母
样例
给出 A = "ABCD" B = "ACD"，返回 true
给出 A = "ABCD" B = "AABC"， 返回 false
解答
思路1
- 将字符串转换成StringBuffer，按字符两次循环比较，A中存在B的字符设置为空
- 不能用deleteChar因为删除字符之后StringBuffer的长度就变化了
- 既然是需要全部存在。内存循环找到后break;内层循环每次检查之后如果有任何一个字符不存在直接返回false，如果程序走到最后还没return fasle,return true即可。
- 整体时间复杂度为O(n^2)，既然题目中说都是大写字符，应该能在这里做文章，得到更快的算法。
代码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种字符可能。
- 字符取值范围确定，就可以用空间复杂度换取时间复杂度。
代码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;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.06.26 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录