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

Question

嗨，我是Python的新手，我想在线性时间内找到文件中的变位符组。Anagram基本上是两个或多个单词，它们由相同的字母表组成，但排列方式不同。

首先，我把所有的单词都读成一张清单。显然，我可以使用基数排序来按列对每个单词进行排序，基数排序应该使用稳定的计数排序。但我不知道我的计数排序应该做什么？我应该写一个计数排序函数，接受一个单词并按字母顺序排序吗？然后按基数排序？

有人能给我一个更清楚的想法来解决这个问题吗？任何帮助都将不胜感激，谢谢！

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;
}