LintCode 58: Compare Strings

题目描述

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

样例

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

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

Fri Mar 17 2017

思路

这道题跟前面一道『两个字符串是变位词』很相似，不同的只是在这题中两个字符串的长度可以不相等。

可以用同样的思路，建一个线性哈希表，统计字符串A中各字符出现的次数，然后再一次减去字符串B中各字符出现的次数，若减到小于0，则可以断定字符串B中存在字符串A中不包含的字符，返回false.

代码

// 比较字符串
class Solution {
public:
    /**
     * @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
     */
    bool compareStrings(string A, string B) {
        if (A.size() < B.size()) return false;
        int count[256] = {0};
        for (string::iterator iter = A.begin(); iter != A.end(); ++iter)
            ++count[*iter];
        for (string::iterator iter = B.begin(); iter != B.end(); ++iter)
        {
            --count[*iter];
            if (count[*iter] < 0) return false;
        }
        return true;
    }
};