Two AC C++ solutions (unordered_map/vector)


  • 15

    The complexity is O(N), N is the length of magazine.

    class Solution {
    public:
        bool canConstruct(string ransomNote, string magazine) {
            unordered_map<char, int> map(26);
            for (int i = 0; i < magazine.size(); ++i)
                ++map[magazine[i]];
            for (int j = 0; j < ransomNote.size(); ++j)
                if (--map[ransomNote[j]] < 0)
                    return false;
            return true;
        }
    };
    

    Or you can use a vector with size 26 instead of an unordered_map.

    class Solution {
    public:
        bool canConstruct(string ransomNote, string magazine) {
            vector<int> vec(26, 0);
            for (int i = 0; i < magazine.size(); ++i)
                ++vec[magazine[i] - 'a'];
            for (int j = 0; j < ransomNote.size(); ++j)
                if (--vec[ransomNote[j] - 'a'] < 0)
                    return false;
            return true;
        }
    };
    

    I remember that there are two variations of this question, perhaps they will come in the next few days :)

    1. If you can only pick letters from the magazine in order.
    2. If the magazine is double sided.

  • 2

    @haruhiku
    Short but bad style of the two :)

    class Solution {
    public:
        bool canConstruct(string ransomNote, string magazine) {
            unordered_map<char, int> map(26);
            for (char mchar : magazine) ++map[mchar];
            for (char rchar : ransomNote) if (--map[rchar] < 0) return false;
            return true;
        }
    };
    
    class Solution {
    public:
        bool canConstruct(string ransomNote, string magazine) {
            vector<int> vec(26, 0);
            for (char mchar : magazine) ++vec[mchar - 'a'];
            for (char rchar : ransomNote) if (--vec[rchar - 'a'] < 0) return false;
            return true;
        }
    };
    

  • 0
    B

    Why do you use map and vector for this question, do these two perform faster compare to other STL for this type of question?


  • 1

    @bill.lv22 For this question, unordered_map performs with amortized O(1) time complexity because you just need to access the bucket/get or update the value in the key-value pair by key and they normally cost constant time. For a fixed size vector (array), access the bucket/update the value by index also cost constant time, which is amortized O(1).

    If you are talking about the real world performance in ms, they may not be the best because there may be some overheads in calculation/memory allocation which affect the running time. If you are talking about the performance in big O notation, these data structures should fit this question very well.


  • 0
    B

    @haruhiku Thank you for replying me.
    I'm a little confused about the real world performance, it seems vector performs better than map, why's that?


  • 1

    @bill.lv22 Before reasoning, there are two things I want to clarify. First, test cases for the OJ are random, so make sure you have the same test cases with the same machine/network condition etc. for your real world performance comparison. Second, make sure you are using unordered_map but not map in C++ because they are different (map is sorted and the corresponding time complexity is in larger scale).

    Now comes the real topic. As I've mentioned, there are some overheads that may affect the real world performance. Take hashmap for example, making key-value pair/calculating hashcode will introduce extra overheads. However, these overheads are negligible when your input is very very large. There are just so many scenarios that one data structure performs "not that efficient" in the real world. Hence, when we talk about efficiency in algorithm/data structure design, we always use big O notation to describe the scale in time/space efficiency.


  • 0
    R

    It will be better if you clarify the size of map, because the process of "resize" will cost too much time.
    Such that:

     unordered_map<char, int> map(26);
    

  • 0
    R

    @ReLing Sorry my English speaking level maybe so low, so thanks if you'd like to point out my problem.


  • 0

    @ReLing I am not sure about the default size of unordered_map, is it smaller than 50? Otherwise it is not likely to get resized that frequently for just 26 letters in total...

    Edit: NVM, I've checked with the OJ, it starts with 1. Thanks for pointing that out.


  • 0
    R

    @haruhiku I have done it and it become more quick.I have find something that the default is 10,Although it isn't 10, I think it is also a good habit.so sorry my expression maybe not well.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.