Valid Anagram
🇷🇺 Название: Допустимая анаграмма
LeetCode: valid-anagram
Временная сложность: O(n)
Пространственная сложность: O(1)
Решение¶
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
counts = [0] * 26
for c1, c2 in zip(s, t):
counts[ord(c1) - ord('a')] += 1
counts[ord(c2) - ord('a')] -= 1
return all(c == 0 for c in counts)
🇺🇸 Условие¶
Given two strings s
and t
, return true
if t
is an anagram of s
, and false
otherwise.
🇷🇺 Условие¶
Примеры¶
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
{
"examples": [
{
"input": {
"s": "anagram",
"t": "nagaram"
},
"output": true
},
{
"input": {
"s": "rat",
"t": "car"
},
"output": false
}
]
}
Ограничения¶
- \(1 \leq s.length, t.length \leq 5 * 10^4\)
s
andt
consist of lowercase English letters.
Потребление ресурсов¶
⏱ Time complexity: O(n)
¶
- Один проход по каждой строке длины
n
, где считаются частоты символов. - Сравнение двух счётчиков также занимает
O(n)
в худшем случае.
Итог: O(n)
🧠 Space complexity: O(1)
¶
- Используется
Counter
или массив фиксированной длины (например,counts[26]
для латиницы). - Память не растёт с длиной строки, только зависит от количества уникальных символов.
Итог: O(1)
(при фиксированном алфавите), иначе O(k)
, где k
— число уникальных символов.
easy hash-table string sorting
Metadata
- title_rus: Допустимая анаграмма
- difficulty: Easy
- leetcode_url: https://leetcode.com/problems/valid-anagram/
- topics: ['Hash Table', 'String', 'Sorting']
- time: O(n)
- space: O(1)
- grind75: True
- tags: ['Easy', 'Hash Table', 'Sorting', '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