383. Ransom Note

这道题也比较简单，通过一个bool数组记录是否已访问过某位置字符即可，但是速度好像很慢，需要好好看看人家怎么写得，时间复杂度O(MN)，空间复杂度O(N)。人家的写法简单很多，时间复杂度O(M+N)，空间复杂度为常数，注意，map可以直接初始化空间大小。

我的解法

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if (ransomNote == ""){
            return true;
        } else if (magazine == ""){
            return false;
        } else{
            bool output = true;
            int noteLength = ransomNote.length();
            bool found [noteLength];
            for (int i = 0; i < noteLength; i++){
                found[i] = false;
            }
            for (int i = 0; i < magazine.length(); i++){
                for (int j = 0; j < noteLength; j++){
                    if (!found[j] && magazine[i] == ransomNote[j]){
                        found[j] = true;
                        break;
                    }
                }
            }
            for (int i = 0; i < noteLength; i++){
                if (!found[i])
                    output = false;
            }
            return output;
        }
    }
};

人家的解法

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

好吧。。。是我太蠢= =