ransom-note

Ransom Note – LeetCode 383

Problem

Description

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.

Example

You may assume that both strings contain only lowercase letters.

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

Answer

Original

Code

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        sort(magazine.begin(),magazine.end());
        sort(ransomNote.begin(),ransomNote.end());
        auto i = ransomNote.begin(), j = magazine.begin();
        while(i != ransomNote.end() && j != magazine.end()){
            if(*i == *j){
                ++i;
                ++j;
            } else if(*i > *j)
                ++j;
            else 
                return false;
        }
        return i == ransomNote.end();
    }
};

思路

先排序再遍历，做复杂了，但是是常数的空间消耗。时间复杂度$O(log{n})$，空间复杂度$O(1)$。

Better

思路

简单的使用数组来保存出现的次数，用空间换时间。时间复杂度$O(n)$，空间复杂度$O(n)$。

Code

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int map[26] = {0};
        for(auto p = magazine.begin(); p != magazine.end(); ++p)
            ++map[*p - 'a'];
        for(auto p = ransomNote.begin(); p != ransomNote.end(); ++p)
            if(--map[*p - 'a'] < 0) return false;
        return true;
    }
};