[LeetCode] 383. Ransom Note, C

Solution  1

• using Hash Map

Intuition

• Declare Hash Map represents charactoer 'a' to 'z' (size 26)
• Increase Hash Map Index which is in Magazine Note
• Decrease Hash Map Index which is in ransom Note
• If one of value in Hash Map under 0, Return false (it means character of Magazine Note doesn't represent ransom Note)
• When you use index, use should consider ASCII number of 'a' at inital index (97)

bool canConstruct(char* ransomNote, char* magazine) {

    int CharNumOfRansomNote = 0;
    int CharNumOfMagazineNote = 0;
    int ArrHashMap[26] = { 0 };
    int ASCIIInitNum = 97;
    bool RetVal = true;


    // Get Num of Char magazine
    while (magazine[CharNumOfMagazineNote] != '\0')
    {
        ++ArrHashMap[magazine[CharNumOfMagazineNote] - ASCIIInitNum];
        ++CharNumOfMagazineNote;
    }

    // Get Num of Char ransomNote
    while (ransomNote[CharNumOfRansomNote] != '\0')
    {
        --ArrHashMap[ransomNote[CharNumOfRansomNote] - ASCIIInitNum];
        
        if (ArrHashMap[ransomNote[CharNumOfRansomNote] - ASCIIInitNum] < 0)
        {
            RetVal = false;
            break;
        }
        else
        {
            // Do Nothing
        }

        ++CharNumOfRansomNote;
    }

    return RetVal;
}

 

 

Solution 2

• Check Character of ransomNote is in Magazine Note
• This solution 'for' statement in 'for' statement

bool canConstruct(char* ransomNote, char* magazine) {

    int CharNumOfRansomNote = 0;
    int CharNumOfMagazineNote = 0;
    int i = 0, j = 0;
    char CharOfRansomNote;
    int FindChar = 0;
    bool RetVal = true;

    // Get Num of Char ransomNote
    while (ransomNote[CharNumOfRansomNote] != '\0')
    {
        ++CharNumOfRansomNote;
    }

    // Get Num of Char magazine
    while (magazine[CharNumOfMagazineNote] != '\0')
    {
        ++CharNumOfMagazineNote;
    }

    FindChar = 1;

    // Check Ransom Note can made by Magazine Note
    for (i = 0; i < CharNumOfRansomNote; ++i)
    {
        CharOfRansomNote = ransomNote[i];

        if (FindChar == 1)
        {
            FindChar = 0;

            for (j = 0; j < CharNumOfMagazineNote; ++j)
            {
                if (FindChar == 0)
                {
                    if (CharOfRansomNote == magazine[j])
                    {
                        FindChar = 1;
                        magazine[j] = '-';
                    }
                    else
                    {
                        // Do Nothing
                    }
                }
                else
                {
                    // Do Nothing
                }
            }

            if (FindChar == 0)
            {
                RetVal = false;
            }
            else
            {
                // Do Nothing
            }
        }
        else
        {
            RetVal = false;
            break;
        }
    }

    return RetVal;
}