LintCode - 比较字符串（普通）

版权声明：本文为博主原创文章，未经博主允许不得转载。

难度：容易

要求：

比较两个字符串A和B，确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母
** 注意事项
在 A 中出现的 B 字符串里的字符不需要连续或者有序。
样例
给出 A = "ABCD"B = "ACD"，返回 true
给出 A = "ABCD" B = "AABC"， 返回 false

思路：
假如A字符串长度为 m，B字符串长度为n，考虑遍历B然后在A中查询是否存在此字符，那么需要遍历次数是 m * n 次而且不能满足B中如果出现重复字母。这时想到了计数排序，用一个临时数组表示A~Z出现的次数，加入'A'在A中出现1次,那么 tmpArr[0] = 1;这时就先遍历A字符，并计数， 然后遍历字符串B 对tmpArr[*]做减法，当这一项的值小于0，表示A中出现此字符的次数不够，可返回失败结果,反之则包含.

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
        int[] countArr = new int[('Z' - 'A' + 1)];//countArr[0]=0 表示有0个'A'
        for(int i = 0; i < A.length(); i++){
            countArr[A.charAt(i) - 'A']++;//对A字符串出现的字符计数
        }   
        for(int i = 0; i < B.length(); i++){
            if(--countArr[B.charAt(i) - 'A'] < 0){
                return false;
            }
        }
        return true;
    }
}