Valid Anagram

Лёгкая№242подсчёт

Даны два слова, s и t. Нужно понять, можно ли переставить буквы s так, чтобы получилось t. Наш пример: «secure» и «rescue» — да, буквы одни и те же, включая две e.

242 Valid AnagramРазбор · 1×

Пример: s = «secure», t = «rescue». Под словами — словарь: буква и её счётчик.

stsecurerescuecount—
ещё не дошлитекущая буквапосчитаносчётчик 0ниже 0анаграмма

В обоих словах по 6 букв: длины совпадают

01/33
сначала · назад · пуск · шаг
Скорость
1function isAnagram(s, t):
2 if len(s) != len(t):
3 return false
4 count = empty map // missing keys: 0
5 for each c in s:
6 count[c] = count[c] + 1
7 for each c in t:
8 count[c] = count[c] - 1
9 if count[c] < 0:
10 return false
11 return true
состояние
count
–
c
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. У анаграмм одни и те же буквы одинаковое число раз, только в другом порядке. Поэтому сравниваем счётчики, а не позиции.
  2. s добавляет единицу за каждую свою букву, t снимает. Счётчик ниже 0 — в t этой буквы больше, чем в s: сразу false.
  3. Длины равны, поэтому если ничего не ушло ниже 0, то и выше 0 ничего не осталось: все счётчики 0, ответ true.

Сложность

Время O(n): по одному проходу по каждому слову. Память O(1): для строчных букв не больше 26 счётчиков, какой бы длины ни были слова.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.