В «Астролите» предметы крафтят из рун. Ходит легенда: если название одного предмета
можно получить, переставив руны в названии другого, то и сам предмет перекуётся в него —
без потерь и без кузнеца.
Даны два названия. Определи, являются ли они анаграммами друг друга, то есть можно ли
переставить руны первого так, чтобы получилось второе.
Входные данные
Два слова, каждое на отдельной строке. Слова состоят из строчных латинских букв и цифр.
Длина каждого слова не превосходит 255.
Выходные данные
Вывести «YES», если слова — анаграммы друг друга, и «NO», если нет. Без кавычек,
заглавными буквами.
Пример
Входные данные:
sharm
marsh
Выходные данные:
YES
Пример
Входные данные:
ananas
nnaass
Выходные данные:
NO
Ограничение. Программа должна работать за O(n): каждую строку можно пройти
считанное число раз, и всё. Сортировка в любом виде запрещена — ни sorted(),
ни свой пузырёк, ни быстрая сортировка. Вызов count() внутри цикла по строке
тоже не годится: он честный, но это скрытые вложенные циклы, то есть O(n²).
Как это оценивается — 5 баллов
- Считаны обе строки; программа сравнивает именно их, а не одну с самой собой.
- Разная длина строк даёт «NO» — либо явной проверкой, либо тем, что счётчики заведомо не сойдутся.
- Заведён подсчёт символов: словарь или массив счётчиков. Учтены и буквы, и цифры — цифры в названиях рун встречаются чаще, чем кажется.
- По первой строке счётчики растут, по второй убывают (или строится второй словарь и сравнивается с первым). Каждая строка пройдена один раз, вложенных циклов по строкам нет.
- Выведено ровно «YES» или «NO» заглавными буквами — судья тут придирчив, как гильдмастер.
Минус. sorted(s) == sorted(t) — решение на одну строку и мимо задачи: это O(n log n), а просили O(n). Красиво, но не туда.