Day3: 30 Day LeetCode May Challenges

problem_statement3.txt

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

RansomNote1.cpp

//TOOK 48 ms
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if(ransomNote.length() == 0 || ransomNote == magazine)
            return true;
        if(ransomNote.length() > magazine.length())
            return false;
        unordered_map<char,int> m1;
        unordered_map<char,int> m2;
        int flag = 0;
        for(char x:ransomNote){
            m1[x]++;
        }
        for(char x:magazine){
            m2[x]++;
        }
        for(auto it1=m1.begin(); it1!=m1.end(); ++it1){
            auto it2 = m2.find(it1->first);
            if(it2!=m2.end()){
                if(m1[it1->first] <= m2[it1->first]){//if(it1->first <= it2->first){
                    //latter takes 52ms to execute,so indexing is better
                    flag = 1;
                    continue;
                }
                else{
                    flag = 0;
                    break;
                }
            }
            else{
                flag = 0;
                break;
            }
        }
        if(flag)
            return true;
        else
            return false;
    }
};

RansomNote2.cpp

//Took 68ms but space wise efficient
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if(ransomNote.length() == 0 || ransomNote == magazine)
            return true;
        if(ransomNote.length() > magazine.length())
            return false;
        unordered_map<char,int> m1;
        int flag = 1;
        for(char x:ransomNote){
            m1[x]++;
        }
        for(char x:magazine){
            auto it = m1.find(x);//I think it is killing time
            if(it!=m1.end())
                m1[x]--;
        }
        for(auto it1 = m1.begin(); it1!=m1.end(); ++it1){
            if(it1->second > 0){
                flag = 0;
                break;
            }
        }
        if(flag)
            return false;
        else
            return true;
    }
};