This is the ninth day of my participation in the First Challenge 2022. For details: First Challenge 2022.

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 69th day 🎈!
🚀 Algorithm 🚀

🌲 : Ransom note

Given a ransom string and a magazine string, determine whether the first string ransom can be formed from characters in the second string magazines. Returns true if it can be formed; Otherwise return false.

In order not to reveal the handwriting of the ransom letter, search the magazine for the letters needed to form a word to express the meaning. Each character in the magazine string can only be used once in the ransom string.

Example 1:

Enter: ransomNote ="a", magazine = "b"Output:false
Copy the code

Example 2:

Enter: ransomNote ="aa", magazine = "ab"Output:false
Copy the code

Example 3:

Enter: ransomNote ="aa", magazine = "aab"Output:true
Copy the code

Tip:

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

🌻C# method: array storage

Use the array to store the number of letters, and then compare the results!

Code:

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        int[] alphabets = new int[26];
        char[] m = magazine.ToCharArray(), r = ransomNote.ToCharArray();
        foreach (char c in m) {
            alphabets[c - 'a'] + +; }foreach (char c in r) {
            if (alphabets[c - 'a'] != 0) alphabets[c - 'a']--;
            else return false;
        }
        return true; }}Copy the code

The execution result

By execution time:76Ms, beat out all Java commits79.50% user memory consumption:42.4MB, beat out all Java commits5.50% of the userCopy the code

🌻Java method: Array storage

Thinking analytical

  • Use arrays A and B to store the number of occurrences of each character in ransomNote and magazine, respectively.

  • If every character in A is less than or equal to every character in B

  • Evaluates to true, and returns false if there is one greater than b

  • This completes the requirement!

Code:

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] a = new int[26];
        int[] b = new int[26];
        char[] aChar = ransomNote.toCharArray();
        char[] bChar = magazine.toCharArray();
        for (int i = 0; i < aChar.length; i++) {
            a[aChar[i] - 'a'] + =1;
        }
        for (int i = 0; i < bChar.length; i++) {
            b[bChar[i] - 'a'] + =1;
        }
        for (int i = 0; i < a.length; i++) {
            if(a[i] > b[i]) {
                return false; }}return true; }}Copy the code

The execution result

By execution time:1Ms, beat out all Java commits90.26% user memory consumption:45.2MB, beat out all Java commits8.05% of the userCopy the code

💬 summary

  • Today is the sixty-ninth day of the buckle algorithm.
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!