如何对文本文件进行排序以在 O(MN) 时间复杂度中查找变位词，其中 M 是最大字符数，N 是单词数？

Question

您好，我是 Python 的新手，我想在文件中找到线性排列的字谜组 time.Anagrams 基本上是两个或更多由相同字母组成但排列不同的单词.

首先，我将所有单词读入一个列表。显然，我可以使用基数排序按列对每个单词进行排序，基数排序应该使用稳定的计数排序。但是我不确切地知道我的计数排序应该做什么？我应该写一个计数排序函数来接受一个单词并按字母顺序对其进行排序吗？然后用基数排序调用它？

有人能告诉我如何解决这个问题吗？任何帮助将不胜感激！

Answer 1

希望对您有所帮助。它也在 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;
}

如何对文本文件进行排序以在 O(MN) 时间复杂度中查找变位词，其中 M 是最大字符数，N 是单词数？

How to sort a text file to find anagrams in O(MN) time complexity where M is the max number of characters and N is the number of words?

python

sorting

radix-sort

counting-sort