“This is the fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

383. The ransom letter

Topic describes

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:

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

Train of thought

To determine whether string A can be composed of characters from string B, we need to count the number of identical characters in two strings. Therefore, we can consider using map, which does not care about character order, so we can use unordered_map. Consider storing characters in A string or B string. Unordered_map is used to store the characters in string B, since it is to determine whether B contains all the characters required by A.

Algorithm steps

• defineunordered_map
• Traversal stringBThe character is stored tomap 中
• Iterate over the string againAIf notmap, return directlyfalse
• If themap, subtract its corresponding value by 1
• Iterate over the stringAAfter the judgementmapIf any value is less than 0, the condition cannot be metfalse
• If no value is less than 0, the condition is satisfied and returnstrue

Using the map

class Solution
{
public:
    bool canConstruct(string ransomNote, string magazine)
    {
        unordered_map<char.int> umap;
        // Add all the characters in the magazine to umap
        for (char c : magazine)
        {
            umap[c] += 1;
        }

        // Query if ransomNote characters are in umap
        // If a character is found in umap, the value is reduced by 1
        // If not, the condition is not met and false is returned
        for (char c : ransomNote)
        {
            auto pos = umap.find(c);
            if(pos ! = umap.end())
            {
                umap[c]--;
            }
            else
            {
                return false; }}// After traversing the ransomNode, check whether the value corresponding to the key in the Umap has a value less than 0
        bool flag = true;
        for (pair<char.int> m : umap)
        {
            // If there is a value less than 0, the condition is not met and false is returned
            if (m.second < 0)
            {
                flag = false; }}returnflag; }};Copy the code

Use an array

Use an array to record the number of occurrences of 26 letters (similar to unordered_map)

class Solution1
{
public:
    bool canConstruct(string ransomNote, string magazine)
    {
        // Only lowercase letters are considered.
        // Initializes a space of 26 characters and records the number of occurrences of each character
        int record[26] = {0};
        // Start by walking through the magazine and counting the number of words in it
        for (char c : magazine)
        {
            record[c - 'a'] + =1;
        }

        // Iterate over ransomNote and subtract the number of characters from it by 1
        for (char c : ransomNote)
        {
            record[c - 'a'] - =1;
        }

        // Iterate through the record array, if there is a value less than 0, the condition is not met
        for (int v : record)
        {
            if (v < 0)
            {
                return false; }}return true; }};Copy the code