Как отсортировать текстовый файл, чтобы найти анаграммы за O(MN) сложности времени, где M - максимальное количество символов, а N - количество слов?

Question

Привет, я новичок в Python и хочу найти группы анаграмм в файле за линейное время. Анаграммы - это, в основном, два или более слов, которые состоят из одного и того же алфавита, но в разных расположениях.

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

Может кто-нибудь дать мне более четкое представление о том, как подойти к этой проблеме? Любая помощь будет оценена спасибо!

Answer 1

Hope this helps you get my approach. It too is in O(mn)

public List<List<String>> groupAnagrams(String[] strs){
    List<List<String>> result = new ArrayList<List<String>>();

    HashMap<ArrayList<Integer>, ArrayList<String>> map = new HashMap<ArrayList<Integer>, HashMap<ArrayList<String>>;

    for(String str : strs){
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i=0; i<str.length(); i++){
            arr[str.charAt(i)- 'a']++;
        }

        if(map.containsKey(arr)){
            map.get(arr).add(str);
        } else {
            ArrayList<String> al = new ArrayList<String>();
            al.add(str);
            map.put(arr, al);
        }
    }

    result.addAll(map.values());

    return result;
}