Valid Anagram

Q: Какова временная сложность задачи «Valid Anagram»?

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

Q: Что лучше использовать при проверке анаграммы: сортировку или подсчёт?

Подсчёт в теории работает быстрее: O(n) против O(n log n) , и его можно остановить, как только какая-либо буква используется слишком часто. Сортировку короче записать, и она работает с любым алфавитом без изменений. На собеседовании сначала расскажи о сортировке, а затем предложи улучшить решение с помощью подсчёта.

ЛегкоХеширование Сортировка

+10

Две строки являются анаграммами, если одна представляет собой перестановку букв другой: в них используются одни и те же буквы, и каждая буква встречается одинаковое количество раз. Даны две строки s и t, состоящие из строчных английских букв. Верните true, если t является анаграммой s, и false в противном случае.

Функция

isAnagram(s: string, t: string) → boolean

sstring: первая строка, строчные буквы
tstring: строка, с которой нужно сравнить s
Возвращаетboolean: истинно, если t использует ровно те же буквы, что и s, каждую — столько же раз

Ограничения

1 ≤ s.length, t.length ≤ 2 × 10⁴
s и t содержат только строчные буквы английского алфавита (от a до z).
Две длины могут различаться.

Примеры

Ввод: s = "listen"t = "silent"
Вывод: true
Пояснение: В обоих словах есть по одной букве e, i, l, n, s и t, поэтому silent — это listen с переставленными буквами.

Ввод: s = "aabb"t = "abbb"
Вывод: false
Пояснение: Длины совпадают, и в обеих строках используются только a и b, но в aabb две буквы a, а в abbb — одна. Количество букв должно совпадать, а не только сами буквы.

Ввод: s = "cat"t = "cast"
Вывод: false
Пояснение: В слове cast четыре буквы, а в слове cat — три, поэтому никакая перестановка букв в cat не позволит написать это слово.

+19 скрытых тестов при отправке

Дополнительный вопрос

Что, если бы строки могли содержать любые символы Unicode вместо символов от a до z? Как бы вы изменили подсчёт?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Анаграмма сохраняет количество каждой буквы, но отбрасывает порядок. Поэтому тебе нужно сводное представление каждой строки, которое не учитывает, где находились буквы, но помнит, сколько букв каждого вида в ней есть. Сортировка строит такое представление за O(n log n); таблица из 26 счётчиков строит его за один проход.

Отсортируйте обе строки

Идея

Сортировка располагает буквы строки в алфавитном порядке и стирает информацию об исходном положении каждой из них. listen сортируется в eilnst, как и silent, поэтому это анаграммы. aabb остаётся aabb, а abbb остаётся abbb; они различаются по индексу 1, поэтому это не анаграммы.

Проверка работает в обоих направлениях. Если t является перестановкой s, то в обеих строках одни и те же буквы встречаются одинаковое число раз, поэтому сортировка даёт одинаковую последовательность. Если отсортированные последовательности равны, то в t используются ровно те же буквы, что и в s.

Сначала сравни длины: строки разной длины никогда не бывают анаграммами, и можно пропустить обе сортировки. Сортировка занимает O(n log n) времени, а большинство языков сортируют копию символов, что требует O(n) дополнительной памяти. При n = 2 × 10^4 это работает быстро, но подход с подсчётом требует меньше операций.

Алгоритм

Если длины s и t различаются, верните false.
Скопируйте символы каждой строки в массив.
Отсортируйте оба массива.
Верните true, если отсортированные массивы равны поэлементно.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Подсчитайте каждую букву

Идея

Могут встречаться только 26 букв, поэтому храни счётчик для каждой буквы в массиве из 26 элементов: с индексом 0 для a и индексом 25 для z. Индекс буквы — это её код символа минус код a. Пройдись по s и увеличивай счётчик каждой буквы на 1, затем пройдись по t и уменьшай его на 1.

Можно остановиться раньше: если счётчик стал меньше 0, значит, в t эта буква встретилась чаще, чем в s. Для aabb и abbb после обработки s счётчики будут такими: a — 2 и b — 2. Затем t три раза встретит b; при третьем разе счётчик b станет равен -1, и сразу нужно вернуть false.

Почему достаточно того, что «ни один счётчик не стал отрицательным»? Длины строк равны, поэтому после обоих проходов сумма счётчиков равна 0. Если ни один счётчик не отрицательный, положительному не с чем было бы уравновеситься, значит, все счётчики равны 0 и количества букв совпадают. Поэтому проверка длины необходима, а не просто служит для ускорения.

Каждая строка считывается один раз, поэтому временная сложность — O(n). В массиве всегда хранится 26 чисел независимо от длины строк, поэтому дополнительная пространственная сложность — O(1).

Алгоритм

Если длины s и t различаются, верни false.
Создай массив из 26 нулей.
Для каждой буквы в s увеличь её счётчик на 1.
Для каждой буквы в t уменьши её счётчик на 1; если он станет меньше 0, верни false.
Верни true.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for ch in t:
        index = ord(ch) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False  # t uses this letter more often than s
    return True

Ловушки и крайние случаи

Большинство неправильных ответов возникает из-за проверки того, какие буквы встречаются, вместо того чтобы проверять, сколько раз они встречаются, или из-за пропуска проверки длины.

Сравнение наборов букв. В aabb и abbb используются одни и те же буквы — a и b, — но это не анаграммы.
Проверка, что каждая буква из t где-то встречается в s, без того чтобы вычёркивать её. aab и abb проходят эту проверку в обоих направлениях.
Пропуск проверки длины в версии с подсчётом. При s = ab и t = a ни один счётчик не опускается ниже 0, поэтому код ошибочно вернёт true.
Использование кода символа напрямую в качестве индекса массива счётчиков. Код символа a равен 97 — это далеко за пределами массива из 26 элементов; сначала вычти код символа a. В Lua и R прибавь 1, поскольку их массивы начинаются с индекса 1.

Частые вопросы4

Какова временная сложность задачи «Valid Anagram»?

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

Что лучше использовать при проверке анаграммы: сортировку или подсчёт?

Подсчёт в теории работает быстрее: O(n) против O(n log n), и его можно остановить, как только какая-либо буква используется слишком часто. Сортировку короче записать, и она работает с любым алфавитом без изменений. На собеседовании сначала расскажи о сортировке, а затем предложи улучшить решение с помощью подсчёта.

Как проверить анаграммы, содержащие символы Unicode?

Замени массив из 26 счётчиков хеш-таблицей, сопоставляющей символы и их количество. Увеличивай счётчик на 1 для каждого символа в s, уменьшай на 1 для каждого символа в t и проверь, что итоговое значение каждого счётчика равно 0. Читай строки посимвольно, а не побайтово, чтобы символ, занимающий несколько байтов, учитывался один раз.

Зачем использовать один массив счётчиков вместо двух?

Два массива, по одному для каждой строки, тоже подойдут: подсчитайте символы в каждой строке, затем сравните массивы. Один массив, значения которого увеличиваются для s и уменьшаются для t, использует вдвое меньше памяти и позволяет вернуть false, как только счётчик становится отрицательным, без итогового цикла сравнения.

Python

def isAnagram(s, t):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

s = "listen"
t = "silent"

Ожидается

true