Як розв’язати задачу з анаграмами: простий посібник

Leetcode 242: Valid Anagram

Вам даються два рядки, s і t. Поверніть True, якщо t є анаграмою s, і False в іншому випадку.

Приклади:

1. Вхід: s = "listen", t = "silent"
   Вихід: True
2. Вхід: s = "apple", t = "applz"
   Вихід: False

Що таке анаграма?

Анаграма — це слово або фраза, утворена перестановкою літер іншого слова чи фрази. Наприклад:

• «listen» і «silent» є анаграмами, оскільки можна переставити літери слова «listen», щоб утворити слово «silent».
• Однак «apple» і «applz» не є анаграмами, оскільки їхні літери не збігаються.

Ваше завдання — визначити, чи є два рядки анаграмами один одного.

Проста розв'язка: сортування

Один із простих способів перевірити, чи є два рядки анаграмами, — це сортувати їхні символи. Якщо відсортовані версії обох рядків однакові, вони є анаграмами.

Кроки алгоритму:

1. Відсортуйте обидва рядки за алфавітом.
2. Порівняйте відсортовані рядки. Якщо вони однакові, поверніть True. В іншому випадку поверніть False.

def isAnagram(s: str, t: str) -> bool:  
 return sorted(s) == sorted(t)

Приклад пояснення:

Припустимо, що s = "listen", а t = "silent".

• Крок 1: Відсортуйте s → sorted(s) = ['e', 'i', 'l', 'n', 's', 't'].
• Крок 2: Відсортуйте t → sorted(t) = ['e', 'i', 'l', 'n', 's', 't'].
• Оскільки відсортовані версії однакові, повертається True.

Часова складність:

1. Сортування кожного рядка займає O(nlog⁡n), де n — довжина рядка.
2. Порівняння двох відсортованих рядків займає O(n).

Загальна складність: O(nlog⁡n)

Просторова складність:

• Сортування створює новий список, тому використовує O(n) додаткового простору.

Оптимізована розв'язка: Хеш-таблиця

Підхід сортування працює, але він не найшвидший. Оптимізуємо!

Замість сортування можна використовувати хеш-таблицю (або Counter в Python), щоб підрахувати частоту кожного символа в обох рядках. Якщо обидва рядки мають однакову частоту символів, вони є анаграмами.

Чому це працює:

Два рядки є анаграмами, якщо для кожного символа:

1. Обидва рядки містять однакові символи.
2. Кількість появ кожного символа однакова.

Кроки алгоритму:

1. Підрахуйте частоту кожного символу в s та t за допомогою хеш-таблиці.
2. Порівняйте дві хеш-таблиці. Якщо вони однакові, поверніть True. В іншому випадку поверніть False.

def isAnagram(self, s: str, t: str) -> bool:  
 hmap = dict()  
 for ch in s:  
 if ch in hmap:  
 hmap[ch] += 1  
 else:  
 hmap[ch] = 1  

 for ch in t:  
 if ch in hmap:  
 hmap[ch] -= 1  
 if hmap[ch] == 0:  
 del hmap[ch]  
 else:  
 return False  

 return len(hmap) == 0

Пояснення:

Давайте розглянемо приклад:
Вхід:
s = "listen"
t = "silent"

Крок 1: Створюємо порожню хеш-таблицю (словар).

Ми починаємо з порожньої хеш-таблиці (hmap), яка буде зберігати кількість символів із рядка s.
hmap = {}

Крок 2: Підраховуємо символи в s.

Ми проходимо по символах у s і оновлюємо хеш-таблицю:

• Для l: hmap = {'l': 1}
• Для i: hmap = {'l': 1, 'i': 1}
• Для s: hmap = {'l': 1, 'i': 1, 's': 1}
• Для t: hmap = {'l': 1, 'i': 1, 's': 1, 't': 1}
• Для e: hmap = {'l': 1, 'i': 1, 's': 1, 't': 1, 'e': 1}
• Для n: hmap = {'l': 1, 'i': 1, 's': 1, 't': 1, 'e': 1, 'n': 1}

Після цього кроку, hmap містить частоту кожного символу в s.

Крок 3: Зменшуємо кількість символів для t.

Тепер ми проходимо по символах у t.
Для кожного символу:

• Якщо символ є в hmap, зменшіть його лічильник.
• Якщо лічильник досягне 0, видаліть символ з hmap.
• Якщо символа немає в hmap, поверніть False (рядки не є анаграмами).
• Для s: hmap = {'l': 1, 'i': 1, 's': 0, 't': 1, 'e': 1, 'n': 1} → Видаліть s, оскільки його лічильник дорівнює 0: hmap = {'l': 1, 'i': 1, 't': 1, 'e': 1, 'n': 1}
• Для i: hmap = {'l': 1, 'i': 0, 't': 1, 'e': 1, 'n': 1} → Видаліть i: hmap = {'l': 1, 't': 1, 'e': 1, 'n': 1}
• Для l: hmap = {'l': 0, 't': 1, 'e': 1, 'n': 1} → Видаліть l: hmap = {'t': 1, 'e': 1, 'n': 1}
• Для e: hmap = {'t': 1, 'e': 0, 'n': 1} → Видаліть e: hmap = {'t': 1, 'n': 1}
• Для n: hmap = {'t': 1, 'n': 0} → Видаліть n: hmap = {'t': 1}
• Для t: hmap = {'t': 0} → Видаліть t: hmap = {}

Після обробки t хеш-таблиця порожня.

Крок 4: Перевірка, чи всі лічильники дорівнюють нулю.

Зрештою, ми перевіряємо, чи порожня хеш-таблиця (len(hmap) == 0). Якщо так, то два рядки є анаграмами. Якщо ні — то вони не є анаграмами.

Для нашого прикладу:
hmap = {} → Хеш-таблиця порожня, отже, повертається True.

Часова складність:

1. Підрахунок символів у s: O(n), де n — довжина рядка s.
2. Обробка символів у t: O(m), де m — довжина рядка t.
3. Загалом: O(n+m).

Оскільки для анаграм n = m, то часова складність спрощується до: O(n).

Просторова складність:

Хеш-таблиця зберігає кількість символів, що залежить від кількості унікальних символів у s чи t. Назвемо це k.

Просторова складність: O(k).

Чому це ефективно?

• Один прохід по кожному рядку: Обидва рядки s і t обробляються лише один раз.
• Без сортування: Сортування зайняло б O(nlog⁡n), але тут ми використовуємо лише лінійні операції.

Ця реалізація є ефективною як по часу, так і по пам'яті, що робить її відмінним рішенням для задачі з анаграмами.

Перекладено з: How to Solve the Anagram Problem: A Simple Guide