题目介绍

给你两个字符串：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 由小写英文字母组成

思路

此题的思路和【LeetCode 350 两个数组的交集 II】一毛一样，核心都是利用哈希表的思想。将magazine中的字母和其出现的次数分别存储起来，再去遍历ransomNote中的字母，进行判断，若出现次数>0,则对其出现的次数-1，遍历下一个字母；若出现的次数==0，则说明 ransomNote 能不能由 magazine 里面的字符构成，返回flase。
1.一维数组实现

bool canConstruct(string ransomNote, string magazine) {
    
	int a[123]={
    0};//小写英文字母z的ascii值122
	for(char x:magazine)
		a[int(x)]++;
	for(char y:ransomNote){
    
		if(a[int(y)]>0)
			a[int(y)]--;
		else
			return 0;
	}
	return 1;
}

2.哈希表实现

bool canConstruct(string ransomNote, string magazine){
    
	unordered_map<char,int>a; //将magazine中的字母和其出现次数分别存储起来
	for(char x:magazine)
		a[x]++;
	for(char y:ransomNote){
    
		if(a[y]>0)
			a[y]--;
		else
			return 0;
	}
	return 1;
}

  在内存消耗上,数组实现要比哈希表实现低一些。