Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
Note: You may assume that both strings contain only lowercase letters.
canConstruct("a", "b") -> false canConstruct("aa", "ab") -> false canConstruct("aa", "aab") -> true
思路：
1. 对于字符串A中的每个字母，都去B中搜，搜到了就从B中删除。 但是空间复杂度比较高。O(m*n)，m为A字符串的长度，n为B字符串长度。 2. 空间换时间。 将字符串A中出现的每个字母，都记录一下次数。看看是不是比B中的次数少。 时间复杂度：O(max(m,n))
public class Solution { public boolean canConstruct(String ransomNote, String magazine) { int[] a = new int[26]; int[] b = new int[26]; for(int i = 0; i < ransomNote.length(); i++){ char tmp = ransomNote.charAt(i); int num = tmp-'a'; a[num]++; } for(int i = 0; i < magazine.length(); i++){ char tmp = magazine.charAt(i); int num = tmp-'a'; b[num]++; } for(int i = 0; i < 26; i++){ if (a[i] > b[i]) return false; } return true; } }