題目連結(https://leetcode.com/problems/ransom-note/description/?envType=study-plan-v2&envId=top-interview-150)
Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
多練習 Hash map 題目,蠻多字串題會用到
ransomNote 和 magazine
true 如果 ransomNote 中的每個字元都可以由 magazine 組成1 <= ransomNote.length, magazine.length <= 105
ransomNote and magazine consist of lowercase English letters.Input: ransomNote = "aa", magazine = "aab"
Output: true
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char, int> mp;
// 統計 magazine 中每個字母的數量
for (char c : magazine) {
mp[c]++;
}
// 檢查 ransomNote 中每個字母
for(char c : ransomNote){
if(mp[c] == 0) return false;
mp[c]--;
}
return true;
}
};
略
1160. Find Words That Can Be Formed by Characters
遍歷字串中每個字母,出現後進行 mp[c]++ 表示出現次數加一,記錄各字母出現次數,再讓 ransomNote 遍歷時減掉字母次數,如果有遇到等於 0 的字母,表示 ransomNote 多出現了不該出現,也就是 magazine 沒有的字母,不符題目規則。
for (char c : magazine) {
mp[c]++;
}
時間與空間的改進:
ps. 部分內容經 AI 協助整理