Ransom Note
🇷🇺 Название: Записка с требованием выкупа
LeetCode: ransom-note
Временная сложность: O(n+m)
Пространственная сложность: O(1)
Решение¶
from collections import Counter
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
r_count = Counter(ransomNote)
m_count = Counter(magazine)
for char in r_count:
if r_count[char] > m_count.get(char, 0):
return False
return True
🇺🇸 Условие¶
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
{
"examples": [
{
"input": {
"ransomNote": "a",
"magazine": "b"
},
"output": false
},
{
"input": {
"ransomNote": "aa",
"magazine": "ab"
},
"output": false
},
{
"input": {
"ransomNote": "aa",
"magazine": "aab"
},
"output": true
}
]
}
Ограничения¶
- \(1 \leq ransomNote.length, magazine.length \leq 10^5\)
ransomNote
andmagazine
consist of lowercase English letters.
Потребление ресурсов¶
⏱ Time complexity: O(n+m)
¶
Counter(ransomNote)
—O(n)
, гдеn = len(ransomNote)
Counter(magazine)
—O(m)
, гдеm = len(magazine)
- Проход по
r_count
— максимумO(k)
, гдеk
— число уникальных символов вransomNote
(в худшем случаеk = 26
для латиницы)
Итог: O(n + m)
🧠 Space complexity: O(1)
¶
Counter
использует память пропорционально количеству уникальных символов.- Для латиницы максимум 26 символов → считается
O(1)
- Если допускать Unicode/большой алфавит →
O(k)
Итог: O(1)
при фиксированном алфавите, иначе O(k)
easy hash-table string counting
Metadata
- title_rus: Записка с требованием выкупа
- difficulty: Easy
- leetcode_url: https://leetcode.com/problems/ransom-note/
- topics: ['Hash Table', 'String', 'Counting']
- time: O(n+m)
- space: O(1)
- grind75: True
- tags: ['Counting', 'Easy', 'Hash Table', 'String', 'problem']
- git_revision_date_localized: 5 июля 2025 г.
- git_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
- git_revision_date_localized_tag:
- git_revision_date_localized_raw_date: 5 июля 2025 г.
- git_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
- git_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
- git_revision_date_localized_raw_iso_date: 2025-07-05
- git_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
- git_revision_date_localized_raw_timeago:
- git_revision_date_localized_raw_custom: 05. июля 2025
- git_site_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
- git_site_revision_date_localized_tag:
- git_site_revision_date_localized: 5 июля 2025 г.
- git_site_revision_date_localized_raw_date: 5 июля 2025 г.
- git_site_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
- git_site_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
- git_site_revision_date_localized_raw_iso_date: 2025-07-05
- git_site_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
- git_site_revision_date_localized_raw_timeago:
- git_site_revision_date_localized_raw_custom: 05. июля 2025