Topic introduction

Here are two strings ：ransomNote and magazine , Judge ransomNote Can it be done by magazine The characters inside make up .
If possible , return true ; Otherwise return to false .
magazine Each character in can only be in ransomNote Used once in .
Example 1

 Input ：ransomNote = "a", magazine = "b"
 Output ：false

Example 2

 Input ：ransomNote = "aa", magazine = "ab"
 Output ：false

Example 3

 Input ：ransomNote = "aa", magazine = "aab"
 Output ：true

Tips

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote and magazine It's made up of lowercase letters

Ideas

The idea and of this question 【LeetCode 350 Intersection of two arrays II】 10 Fen is the same , The core is to use the idea of hash table . take magazine The letters in and the number of times they appear are stored separately , And then go through ransomNote Letters in , Judge , If the number of occurrences >0, The number of times it appears -1, Traverse the next letter ; If the number of occurrences ==0, shows ransomNote Can it be done by magazine The characters inside make up , return flase.
1. One dimensional array implementation

bool canConstruct(string ransomNote, string magazine) {
    
	int a[123]={
    0};// Small letters z Of ascii value 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. Hash table implementation

bool canConstruct(string ransomNote, string magazine){
    
	unordered_map<char,int>a; // take magazine The letters in and their occurrences are stored separately 
	for(char x:magazine)
		a[x]++;
	for(char y:ransomNote){
    
		if(a[y]>0)
			a[y]--;
		else
			return 0;
	}
	return 1;
}

   On memory consumption , The array implementation is lower than the hash table implementation .