Ransom Note

🏠 ⬅️ ➡️

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example 1:

Input: ransomNote = "a", magazine = "b" Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab" Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab" Output: true

Constraints:

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote and magazine consist of lowercase English letters.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=:), allocatable :: ransomNote, magazine
    logical :: result

    ! Example 1
    allocate(character(len=1) :: ransomNote)
    allocate(character(len=1) :: magazine)
    ransomNote = 'a'
    magazine = 'b'
    result = canConstruct(ransomNote, magazine)
    print *, result
    deallocate(ransomNote)
    deallocate(magazine)

    ! Example 2
    allocate(character(len=2) :: ransomNote)
    allocate(character(len=2) :: magazine)
    ransomNote = 'aa'
    magazine = 'ab'
    result = canConstruct(ransomNote, magazine)
    print *, result
    deallocate(ransomNote)
    deallocate(magazine)

    ! Example 3
    allocate(character(len=2) :: ransomNote)
    allocate(character(len=3) :: magazine)
    ransomNote = 'aa'
    magazine = 'aab'
    result = canConstruct(ransomNote, magazine)
    print *, result
    deallocate(ransomNote)
    deallocate(magazine)

contains

    function canConstruct(ransomNote, magazine) result(result_)
        implicit none
        character(len=*), intent(in) :: ransomNote, magazine
        integer :: i, j
        logical :: result_

        do i = 1, len(ransomNote)
            do j = 1, len(magazine)
                if (ransomNote(i:i) == magazine(j:j)) then
                    magazine(j:j) = ' '
                    exit
                end if
            end do
            if (j > len(magazine)) then
                result_ = .false.
                return
            end if
        end do

        result_ = .true.
    end function canConstruct
end program main
❌ Compiled
❌ Executed
❌ Correct 
module main

implicit none

interface

    function canConstruct(ransomNote, magazine) result(output)
        implicit none
        character(len=*), intent(in) :: ransomNote, magazine
        logical :: output
    end function canConstruct

end interface

! Test cases
character(len=100) :: ransomNote, magazine
logical :: output

! Test case 1
ransomNote = "a"
magazine = "b"
output = canConstruct(ransomNote, magazine)
if (output) then
    write (*,*) "Test case 1: FAILED"
else
    write (*,*) "Test case 1: PASSED"
end if

! Test case 2
ransomNote = "aa"
magazine = "ab"
output = canConstruct(ransomNote, magazine)
if (output) then
    write (*,*) "Test case 2: FAILED"
else
    write (*,*) "Test case 2: PASSED"
end if

! Test case 3
ransomNote = "aa"
magazine = "aab"
output = canConstruct(ransomNote, magazine)
if (output) then
    write (*,*) "Test case 3: PASSED"
else
    write (*,*) "Test case 3: FAILED"
end if

contains

function canConstruct(ransomNote, magazine) result(output)
    implicit none
    character(len=*), intent(in) :: ransomNote, magazine
    integer :: i, j
    logical :: output

    ! Initialize the output variable
    output = .false.

    ! Loop through each character in ransomNote
    do i = 1, len(ransomNote)
        ! Loop through each character in magazine
        do j = 1, len(magazine)
            ! If the current character in ransomNote matches the current character in magazine
            if (ransomNote(i:i) == magazine(j:j)) then
                ! If the current character in magazine is the last character in magazine
                if (j == len(magazine)) then
                    ! Set the output variable to true
                    output = .true.
                    ! Exit the loop
                    exit
                ! Otherwise, continue looping
                else
                    cycle
                end if
            end if
        end do
        ! If the output variable is still false, then the current character in ransomNote cannot be constructed
        if (.not. output) then
            exit
        end if
    end do

end function canConstruct

end program main
🌐 Data from online sources 
def can_construct(ransom_note, magazine):
    letter_count = {}

    for c in magazine:
        letter_count[c] = letter_count.get(c, 0) + 1

    for c in ransom_note:
        if c not in letter_count or letter_count[c] == 0:
            return False
        letter_count[c] -= 1

    return True

The algorithm works as follows: 1. Create a hash map called letterCount, which holds the count of each character in the magazine string. 2. Iterate over the characters in ransomNote. For each character: a. If the character is not in letterCount or its count is 0, return false, as the required letter is not available in magazine. b. Decrease the count of the character in letterCount by 1. 3. Once the iteration is done, if the entire ransomNote string is processed without any issue, return true.

This algorithm checks if the ransomNote can be made from the available characters in the magazine by using a single pass through each string and maintaining the count of characters in a hash map.

🌐 Data from online sources 
#include <string>
#include <unordered_map>

bool canConstruct(std::string ransomNote, std::string magazine) {
    std::unordered_map<char, int> letterCount;
    for (char c : magazine) {
        letterCount[c]++;
    }

    for (char c : ransomNote) {
        if (letterCount[c] == 0) {
            return false;
        }
        letterCount[c]--;
    }

    return true;
}

The algorithm works as follows: 1. Create a hash map called letterCount, which holds the count of each character in the magazine string. 2. Iterate over the characters in ransomNote. For each character: a. If the character is not in letterCount or its count is 0, return false, as the required letter is not available in magazine. b. Decrease the count of the character in letterCount by 1. 3. Once the iteration is done, if the entire ransomNote string is processed without any issue, return true.

This algorithm checks if the ransomNote can be made from the available characters in the magazine by using a single pass through each string and maintaining the count of characters in a hash map.