“This is the 20th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Hey, guys. I’m your balls.

Today solve the ransom letter, continue to hash table combat series of problems.

Don’t say a word. Just turn it on.

LeetCode 383: Ransom letter

In order not to reveal the handwriting of the ransom letter, search the magazine for the letters needed to form words to express the meaning.

The question

Given a ransom string and a magazine string.

Determine if ransom can be made up of strings in the magazine. Can return True, otherwise return False.

The sample

Enter: ransomNote = “anagram”, magazine = “nagaram”

Output: true,

prompt

  • You can assume that both strings contain only lowercase letters.

title

Water problem, the difficulty is simple.

I find that when I buckle up a lot of titles, at first glance, I feel like: “Oh my God? You can tell by the headline that I won’t do it.

When you see the meaning of the question, your mental activity becomes: “Huh? Is this it?” .

Maybe that’s why… Duel?

This question is very similar to the one we did on valid letter heterotopic words. If you forget it, read the article:

ACM player graphic force button valid letter heterotopic word!

A valid alphabetic alloword is to find out if the strings S and t can be composed of each other.

This ransomNote is asking if the string magazine can form the string ransomNote, regardless of whether the string ransomNote can form the string magazine.

With that in mind, the key point is that both strings contain only lowercase letters, and there are a fixed 26 lowercase letters.

This is a fixed length range and it depends on the number of characters, so it’s okay to hash.

The next thing is to find the hash function, which is to put each key in the range of 0 to N minus 1 and put it in the right place.

The hash function f of key is equal to key – ‘A’. This is actually an operation on the ASCII characters, the ASCII characters of the letters A to Z are 26 consecutive numeric values.

For example, f(a) = ‘a’ – ‘a’ = 0, f(b) = ‘b’ – ‘a’ = 1, that is, the letter A corresponds to the hash table with index 0, the letter B corresponds to the hash table with index 1, and so on.

Hash function, the following is very simple:

  • Iterating through the magazine string, the corresponding character in the hash table increases.
  • Iterate over the ransomNote string, subtracting the corresponding character in the hash table by one. If the value at that position is 0 before subtracting by one, then there are not enough characters in the magazine to build ransomNote, returning False.
  • When traversal is complete, return True.

The illustration

Take ransomNote = “anagram”, magazine = “nagaram” for example.

First, initialize the hash table. According to the hash function, the position of the letters a ~ z in the hash table is as follows:

The first step is to iterate through the string magazine and encounter the character that corresponds to the hash value of the subscript + 1.

For magazine = “nagaram”, the first character is n, and the subscript of n is 13, then the subscript of 13 is +1:

Hash [ord(I) -ord ('a')] += 1 hash[ord(I) -ord ('a')] += 1Copy the code

After iterating through the string magazine, the hash table looks like this:

The second step is to iterate over the string ransomNote, subtracting the corresponding character from the hash table by one. If the value at that position is 0 before subtracting by one, then there are not enough characters in the magazine to build ransomNote, returning False.

If ransomNote = “anagram”, the first character is a and the subscript of a is 0, then the subscript 0 corresponds to -1:

Hash [ord(I) -ord ('a')] == 0: hash[ord(I) -ord ('a')] == 0: Return False # Otherwise, subtract characters from the hash else: hash[ord(I) -ord ('a')] -= 1Copy the code

Similarly, after iterating through the string ransomNote, the hash table looks like this:

Step 3, after traversal, return True.

The time complexity of this method is O(n).

Because we opened an additional array of length 26, the space complexity is O(m), where m = 26.

Code implementation

Python code implementation

class Solution: def canConstruct(self, ransomNote: str, magazine: str) -> bool: Hash = [0] * 26 hash = [0] * 26 hash = [0] * 26 hash[ord(i) - ord('a')] += 1 for i in ransomNote: Hash [ord(I) -ord ('a')] == 0: hash[ord(I) -ord ('a')] Else: hash[ord(I) -ord ('a')] -= 1 return TrueCopy the code

Java code implementation

class Solution { public boolean canConstruct(String ransomNote, String magazine) { int[] arr = new int[26]; int temp; for (int i = 0; i < magazine.length(); i++) { temp = magazine.charAt(i) - 'a'; arr[temp]++; } for (int i = 0; i < ransomNote.length(); i++) { temp = ransomNote.charAt(i) - 'a'; If (arr[temp] > 0) {arr[temp]--; if (arr[temp] > 0) {arr[temp]--; } else { return false; } } return true; }}Copy the code

This is the end of the ransom letter hot, two questions in a row, do you feel hot for this kind of question?

If you don’t feel it, you still have to think about it and apply it to future problems.

Please give me a thumbs up.

I’m Handsome. I’ll see you next time.