这道题也比较简单，通过一个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;
}
};
好吧。。。是我太蠢= =
