“This is my 35th day of participating in the First Challenge 2022. For more details: First Challenge 2022.”

The ransom letter

Topic describes

Give you two strings: ransomNote and magazine. Determine if ransomNote can be composed of characters from the magazine. If so, return true; Otherwise return false. Each character in the magazine can only be used once in ransomNote. Example 1:

Input: ransomNote = "a", magazine = "b" Output: falseCopy the code

Example 2:

Input: ransomNote = "aa", magazine = "ab" Output: falseCopy the code

Example 3:

Input: ransomNote = "aa", magazine = "aab" Output: trueCopy the code

Algorithm analysis

This is essentially looking at the use of hash tables. Because in general, a hash table is used to quickly determine whether an element appears in the collection, in ontology, actually is to judge whether the elements of the string ransomNote contains a collection of elements in the magazine, now that USES hash method here, then we will first to learn about the related concepts of hash table!!!! The basic idea of hashing:

Establish a definite correspondence between the record key code and the storage address, and obtain the address of the record to be checked through calculation. Hash table: Using hash technology to find the contiguous storage space of the search set. Hash function: A function that maps keycodes to the appropriate storage location in a hash table. Hash address: The storage address obtained by the hash function.

In this case, to determine whether the elements of the string ransomNote are contained by the collection of elements in the magazine, we first construct an array hash of 26 letters. Then iterate over both strings, doing the following in the array hash: 1. First of all, the string in the magazine is converted into a character array, where the key code is 26 English children and mother, and then the character array is traversed in turn, and the number of times the letter appears is filled in below the letter. 2. Convert the string in the ransomNote to an array of characters and iterate: When the number of characters in the ransomNote is greater than 0, subtract 1 from the number. If the number is less than or equal to 0, return false

Code parsing

class Solution { public boolean canConstruct(String ransomNote, String magazine) {// Create an array of 26 English words hash int[] hash=new int[26]; For (char c: magazine.tocharArray ()){hash[c-'a']++; hash[c-'a']++; } char c: ransomnote.tochararray () {char c: ransomnote.tochararray (); Otherwise return false if(hash[c-'a']>0){hash[c-'a']--; }else{ return false; } } return true; }}Copy the code