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