這道題也比較簡單宛官，通過一個bool數(shù)組記錄是否已訪問過某位置字符即可瓦糕，但是速度好像很慢，需要好好看看人家怎么寫得咕娄，時間復雜度O(MN)，空間復雜度O(N)。人家的寫法簡單很多费变，時間復雜度O(M+N)，空間復雜度為常數(shù)挚歧，注意扛稽，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;
}
};
好吧滑负。在张。。是我太蠢= =
