Valid Anagram

Ссылка с заданием на литкоде

Описание

Необходимо проверить является ли строка t анаграммой для строки s. Если строки являются анaграмами, вернуть true, иначе вернуть false.

Анаграммой является слово или фраза составляенная путём перестановки другой строки или фразы. Обычно используются все символы исходной строки в том колличстве, в котором они представлены в исходной строке.

Пример 1:

Входные данные: s = "anagram", t = "nagaram" Выходные данные: true Объяснение: строка "nagaram" является перестановкой строки "anagram"

Пример 2:

Входные данные: s = "rat", t = "car" Выходные данные: false

Пример 3:

Входные данные: s = "", t = ""
Выходные данные: true

---

Идея решения

Поскольку нам нужно проверить является ли одна строка перестановкой другой, то первой же идеей приходит отсортировать строки и сравнить их. Такой подход, хоть и сработает, будут неэффективным. Для оптимизации мы можем воспользоваться хэш-таблицами.

Важно отметить, что хоть в описании и написано, что "обычно" строки имеют одинковое количество символов, от нас ожидают, что именно так и будет. Другими словами, необходимо вернуть true в том лишь случае, когда обе строки имеют одинаковый набор символов, а количество вхождений каждого символа одинаковое в обоих строках. Это уточнение так же является подсказкой к оптимальному решению.

Алгоритм решения

Для оптимального решения нам необходимо создать хэш-таблицу, в которой ключами будут уникальные символы строки, а значениями их количество в строке. В языке Python для этого мы можем использовать тип данных Counter. Получив символы и их количество в первой и второй строке необходимо их сравнить. Несмотря на то, что мы проходим сначала обе строки, а затем для сравнения ещё раз все уникальные символы, сложность будет линейной. В качестве ускорения можно делать сравнение во время прохода по второй строке, увеличивая счётчик при проходе первой строки и уменьшая при проходе по второй. Так же для ускорения сравним длины строк и множества символов в каждой строке до выполнения алгоритма.

Таким образом наш алгоритм выглядит так: 1. Сравниваем длину и уникальные символы строк 2. Создаём хэш-таблицу символ: кол-во вхождений в строку 3. Сравниваем количество вхождений символов в обе строки

Сложность

• По времени: \(O(N + M)\) n = len(s), m = len(t) Для того, что бы проверить, что строки не являются анограмами, мы приведём их к множеству, что требует прохода по каждой из них. Далее необходимо сравнить количество вхождений уникальных символов в каждую строку.

В итоге, в худшем случае, нам потребуется N + M + N + N, сложность линейная.

• По памяти: \(O(N)\) n = len(set(s) | set(t)) Для хранения создаётся две хэш-таблицы с ключами уникальными значениями в каждой строке.

Код решения:

На Python можно решить одной строкой return Counter(s) == Counter(t).

PythonRust

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        set_s = set(s)
        set_t = set(t)
        if len(s) != len(t) or set_s != set_t:
            return False

        counter_s = {}
        counter_t = {}

        for ltr_s, ltr_t in zip(s, t):
            counter_s[ltr_s] = counter_s.get(ltr_s, 0) + 1
            counter_t[ltr_t] = counter_t.get(ltr_t, 0) + 1

        return counter_s == counter_t

use std::collections::{HashSet, HashMap};

impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        let set_s: HashSet<char> = s.chars().collect();
        let set_t: HashSet<char> = t.chars().collect();
        if s.len() != t.len() || set_s != set_t{
            return false;
        }

        let mut counter_s: HashMap<char, i32> = HashMap::new();
        let mut counter_t: HashMap<char, i32> = HashMap::new();

        for (ltr_s, ltr_t) in s.chars().zip(t.chars()) {
            *counter_s.entry(ltr_s).or_insert(0) += 1;
            *counter_t.entry(ltr_t).or_insert(0) += 1;
        }

        counter_s == counter_t
    }
}