题目

描述

比较两个字符串A和B，确定A中是否包含B中所有的字符。字符串A和B中的字符都是大写字母

样例

给出 A = "ABCD" B = "ACD"，返回 true
给出 A = "ABCD" B = "AABC"， 返回 false

解答

思路1

1. 将字符串转换成StringBuffer，按字符两次循环比较，A中存在B的字符设置为空
2. 不能用deleteChar因为删除字符之后StringBuffer的长度就变化了
3. 既然是需要全部存在。内存循环找到后break;内层循环每次检查之后如果有任何一个字符不存在直接返回false，如果程序走到最后还没return fasle,return true即可。
4. 整体时间复杂度为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

1. 既然都是大写字母，那么只有26种字符可能。
2. 字符取值范围确定，就可以用空间复杂度换取时间复杂度。

代码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;
    }
}