Перейти к содержанию

Название задания

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

Описание

Строки в полученом массиве strs необходимо сгруппировать по анаграммам. Порядок строк и групп в выходном массиве не имеет значения.

Пример 1:

Входные данные: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
Выходные данные: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
Объяснение: каждая строка относиться к той группе в которой все строки являются анограммами

Пример 2:

Входные данные: strs = [""]
Выходные данные: [[""]]

Пример 3:

Входные данные: strs = ["a"]
Выходные данные: [["a"]]

Идея решения

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

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

Для решения этой задачи будем использовать хэш-таблицу. Ключами будет множество отсортированных строк. Значением для каждого ключа будут все входящие в полученный массив вариации анаграммы.

Алгоритм на Rust аналогично решению на Python, но в связи с особенностями работы с памятью требует дополнительных действий.

Таким образом наш алгоритм выглядит так: 1. создаём хэш-структуру storage для хренения пар анаграмм:вариациий 2. итеруемся по полученному массиву строк и сохраняем отсортированную строку 3. добавляем текущую строку в массив хранящийся в storage по хэшу отсортированной строки 4. Возвращаем массив всех значений из storage

Сложность

  • По времени: \(O(N * K log K)\) n = len(strs), k = avg([len(i) for i in strs]) Алгоритм состоит из нескольких действий:
  • итерация по массиву строк, если длина строки равна n то алгоритму потребуется сделать n операций
  • для каждой строки вызывается сортировка, которая имеет сложность \(O(N log N)\), k равна средней длине строк
  • производится вставка в словарь с созданием пустого списка или добавление в список, в средем эта операция происходит за константное время
  • в среднем сбор значений из хэш-таблицы выполняется за линейное время и определяется количеством ключей

В данном алгоритме "узким местом" или "бутылочным горлышком" является сортировка. Зная, что входные данные консистентны, и всегда состоят исключительно из символов латинского алфавита в нижем регистре, то можно использовать более подходящий алгоритм сортировки. При использовании сортировки подсчётом можно оптимизировать решение до линейного.

  • По памяти: \(O(N * K)\) n = len(strs), k = avg([len(i) for i in strs]) Для реализации алгоритма необходимо хранить все варианты анаграмм. В худшем случае, когда все строки уникальны после сортировки, потребуется хранить каждую строку вместе с её отсортированной версией.

Код решения:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        storage = defaultdict(list)

        for word in strs:
            storage["".join(sorted(word))].append(word)

        return storage.values()

use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let mut storage: HashMap<String, Vec<String>> = HashMap::new();

        for word in strs {
            let mut chars: Vec<char> = word.chars().collect();
            chars.sort_unstable();
            let word_sorted = chars.into_iter().collect::<String>();
            storage.entry(word_sorted).or_insert(Vec::new()).push(word);
        }
        storage.values().map(|v| v.clone()).collect()
    }
}