Алгоритми та структури даних · Junior · Запитання 44 з 75
Як за O(n) перевірити, що два рядки є анаграмами?
- 1Перевірити, що рядки однакової довжини
- 2Перевірити, що кожен символ першого рядка є в другому
- ✓Правильна відповідь: Порахувати символи обох рядків і порівняти лічильники
Пояснення
Порахуйте символи першого рядка в map, відніміть другий рядок і перевірте, що всі лічильники нульові. Однакової довжини замало, а перевірка «кожен символ є» ігнорує, скільки разів він трапляється ("aab" і "abb"). Сортування обох рядків теж працює, але за O(n log n).