Lintcode: Compare Strings

Compare two strings A and B, determine whether A contains all of the characters in B.

The characters in string A and B are all Upper Case letters.

Example

For A = "ABCD", B = "ACD", return true.

For A = "ABCD", B = "AABC", return false.

Create a hashmap from A and then search each letter of B.

way 1: Create two hashmaps and then compare frequencies.
If frequency of a letter in B is larger than A, return false;
http://www.cnblogs.com/EdwardLiu/p/4273817.html

way 2: If the letter frequency equals zero, return false; Else reduce the corresponding times.
http://www.cnblogs.com/lishiblog/p/4194945.html

way 3: Reduce the corresponding frequency. If the letter frequency is less than zero, return false.
http://algorithm.yuanbin.me/string/compare_strings.html


In c++, hashmap can be unordered_map or array(size 26).

unordered_map version:

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) {
        unordered_map<char, int> mA;
        for(auto c: A){
            mA[c]++;
        }
        for(auto b: B){
            mA[b]--;
            if(mA[b] < 0) return false;
        }
        return true;
    }
};

array version:

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) {
        int mA[26] = {0};
        for(auto a: A){
            mA[a - 'A']++;
        }
        //way 1
        int mB[26] = {0};
        for(auto b: B){
            mB[b - 'A']++;
            if(mB[b - 'A'] > mA[b - 'A']) return false;
        }
        return true;
        //way 2
        for(auto b: B){
            mA[b - 'A']--;
            if(mA[b - 'A'] < 0) return false;
        }
        return true;
        //way 3
        for(auto b: B){
            if(mA[b - 'A'] == 0) return false;
            mA[b - 'A']--;
        }
        return true;
    }
};