Ransom Note

Data Structures and Algorithms

Statement

Given two strings note and magazine, find if note can be constructed using the characters from magazine. Return true if it can be constructed, false otherwise.

Constraints

• 1 ≤ note.length(), magazine.length() ≤ 10³
• note and magazine contain lowercase English characters

Solution

"""
production algorithm
"""

from collections import Counter


class Solution:
    def can_construct(self, note, magazine):
        """
        time complexity O(n + m)
        space complexity O(1)
        """
        counter = Counter(magazine)
        for char in note:
            if char not in counter or counter[char] == 0:
                return False
            counter[char] -= 1
        return True

"""
unit tests
"""

from unittest import TestCase
from algorithms.counters.ransom_note.solution import Solution


class SolutionTestCase(TestCase):
    def test_character_mismatch(self):
        # Given
        note = "meetinthealley"
        magazine = "meetinthealle"
        solution = Solution()

        # When
        actual = solution.can_construct(note, magazine)

        # Then
        expected = False
        self.assertEqual(actual, expected)

    def test_character_frequency_mismatch(self):
        # Given
        note = "meetinthealley"
        magazine = "metinthealley"
        solution = Solution()

        # When
        actual = solution.can_construct(note, magazine)

        # Then
        expected = False
        self.assertEqual(actual, expected)

    def test_ransom_note_construction_succeeds(self):
        # Given
        note = "meetinthealley"
        magazine = "meetinthealley"
        solution = Solution()

        # When
        actual = solution.can_construct(note, magazine)

        # Then
        expected = True
        self.assertEqual(actual, expected)

Strategy

Counters.

Explanation

The algorithm counts the frequencies of all characters in magazine. Then, the algorithm iterates the characters of note. If there exists some character in note that doesn’t exist in magazine, or all occurrences of it in magazine have already been used in construction of note, then return false since construction of note cannot be completed. After iteration of the characters of note completes, return true since construction of note can be completed.

Time Complexity

Let n be the number of characters in note, and m be the number of characters in magazine. At most, iteration of all characters of note and magazine occurs. Therefore, the time complexity of the algorithm is O(n + m).

Space Complexity

At most, there are 26 unique characters since all characters are lowercase English characters. In other words, there’s a constant number of characters in the characters frequencies counter. Therefore, the auxiliary space complexity of the algorithm is O(1).

Links

data_structures_algorithms/algorithms/counters/ransom_note at main ·…