優質博文：IT-BLOG-CN

一、題目

給你兩個字符串：ransomNote和magazine，判斷ransomNote能不能由magazine里面的字符構成。如果可以，返回true；否則返回false。magazine中的每個字符只能在ransomNote中使用一次。

示例 1：
輸入：ransomNote = "a", magazine = "b"
輸出：false

示例 2：
輸入：ransomNote = "aa", magazine = "ab"
輸出：false

示例 3：
輸入：ransomNote = "aa", magazine = "aab"
輸出：true

1 <= ransomNote.length, magazine.length <= 105
ransomNote和magazine由小寫英文字母組成

二、代碼

【1】Map： 創建一個Map,key存放magazine字符，value存放count, 遍歷ransomNote對count進行減小，如果小于0，說明不包含直接退出。

class Solution {public boolean canConstruct(String ransomNote, String magazine) {// 創建一個Map, key 存放 magazine 字符，value存放count, 遍歷 ransomNote 對 count進行減小，如果小于0，說明不包含Map<Character, Integer> map = new HashMap();for (int i = 0; i < magazine.length(); i++) {map.put(magazine.charAt(i), map.getOrDefault(magazine.charAt(i), 0) + 1);}for (int i = 0; i < ransomNote.length(); i++) {int count = map.getOrDefault(ransomNote.charAt(i), 0);map.put(ransomNote.charAt(i), --count);if (count < 0) {return false;}}return true;}
}

時間復雜度： O(m+n)其中m表示ransomNote的長度，n表示magazine的長度。
空間復雜度： O(m)其中m表示ransomNote的長度。

【2】字符統計： 如果字符串magazine的長度小于字符串ransomNote的長度，則我們可以肯定magazine無法構成ransomNote，此時直接返回false。首先統計magazine中每個英文字母a的次數cnt[a]，再遍歷統計ransomNote中每個英文字母的次數，如果發現ransomNote中存在某個英文字母c的統計次數大于magazine中該字母統計次數cnt[c]，則此時我們直接返回false。

class Solution {public boolean canConstruct(String ransomNote, String magazine) {if (ransomNote.length() > magazine.length()) {return false;}// 創建一個26個字母長度的數組，下標表示字母，value表示個數int[] letter = new int[26];for (char c : magazine.toCharArray()) {letter[c - 'a']++;}for (char c : ransomNote.toCharArray()) {letter[c - 'a']--;if (letter[c - 'a'] < 0) {return false;}}return true;}
}

時間復雜度： O(m+n)其中m是字符串ransomNote的長度，n是字符串magazine的長度，我們只需要遍歷兩個字符一次即可。
空間復雜度： O(∣S∣)，S是字符集，這道題中S為全部小寫英語字母，因此∣S∣=26。

【3】哈希表或數組： 我們可以用一個哈希表或長度為26的數組cnt記錄字符串magazine中所有字符出現的次數。然后遍歷字符串ransomNote，對于其中的每個字符c，我們將其從cnt的次數減1，如果減1之后的次數小于0，說明c在magazine中出現的次數不夠，因此無法構成ransomNote，返回false即可。

否則，遍歷結束后，說明ransomNote中的每個字符都可以在magazine中找到對應的字符，因此返回true。

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] cnt = new int[26];for (int i = 0; i < magazine.length(); ++i) {++cnt[magazine.charAt(i) - 'a'];}for (int i = 0; i < ransomNote.length(); ++i) {if (--cnt[ransomNote.charAt(i) - 'a'] < 0) {return false;}}return true;}
}

時間復雜度： O(m+n)，其中m和n分別為字符串ransomNote和magazine的長度；
空間復雜度： O(C)，而C為字符集的大小，本題中C = 26；

【4】枚舉： 把26字母中出現的字母全部統計一遍到數組中，然后遍歷我們組成字符串（字符串轉成字符數組），對出現的字母相減，減出來到最后，數組中沒有出現小于0的數就是可以組成，相反不能組成

class Solution {public static boolean canConstruct(String ransomNote, String magazine) {int [] ans = new int[26];// 將字符串中的字符轉換為字符數組for(char c : magazine.toCharArray()){// 26個字母 出現多少次ans[c-'a']++;}for (char c : ransomNote.toCharArray()){if(--ans[c - 'a'] < 0){return false;}}return true;}
}

時間復雜度： O(1)
空間復雜度： O(1)