如何排序文本文件以查找O（MN）时间复杂度的字谜，其中M是最大字符数，N是单词数？

Question

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

首先，我将所有单词读入列表。显然，我可以使用基数排序按列对每个单词进行排序，并且基数排序应使用稳定的计数排序。但是我不确切知道我的计数排序应该怎么做？我是否应该编写一个包含单词并按字母顺序排序的计数排序功能？然后以基数排序称呼它吗？

有人可以给我一个更清晰的方法来解决这个问题吗？感谢您的帮助！

Answer 1

希望这对您有所帮助。也是O（mn）public List<List<String>> groupAnagrams(String[] strs){&nbsp; &nbsp; List<List<String>> result = new ArrayList<List<String>>();&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; HashMap<ArrayList<Integer>, ArrayList<String>> map = new HashMap<ArrayList<Integer>, HashMap<ArrayList<String>>;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; for(String str : strs){&nbsp; &nbsp; &nbsp; &nbsp; ArrayList<Integer> arr = new ArrayList<Integer>();&nbsp; &nbsp; &nbsp; &nbsp; for(int i=0; i<str.length(); i++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; arr[str.charAt(i)- 'a']++;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; if(map.containsKey(arr)){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; map.get(arr).add(str);&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ArrayList<String> al = new ArrayList<String>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; al.add(str);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; map.put(arr, al);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; result.addAll(map.values());&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; return result;}