【hot100】跟着小王一起刷leetcode -- 49. 字母异位词分组
【hot100】跟着小王一起刷leetcode -- 49. 字母异位词分组
49. 字母异位词分组
题目解读
ok，兄弟们，咱们来看看这道题，很明显哈，这里的关键词是字母异位词，这是啥意思呢？
我们读一下题目，其实就发现很简单，两个词，如果对字母重新排列之后是相同的，那么这俩就是字母异位词，举个例子哈
ate可以排列为eat，aet也可以重新排列为eat，那么这三个词就是字母异位词。
这个题让我们对给出的词进行分组，互为字母异位词的存放在一起，那咱们来看看咋做吧。
解题思路
看了刚才的题目介绍，想必你已经有了想法，我把这些词的字母按顺序排列下，然后把相同的放在一起不就做完了吗！
确实，这个想法是可行的，然后你采用最简单的插入排序排了一下，然后发现ac了。 但当你看到时间复杂度的时候，你陷入了沉思
这。。。。。
来看看咋改良把，很明显哈，咱们的排序肯定是浪费时间的，那考虑下怎么才能在O(n)时间完成排序呢？或则有没有其他方法可以起到和排序一样的作用呢？
很明显，O(n)时间有点困难，那怎么代替排序呢？
现在想想，无非是把这些词的字母按照顺序存放起来，那这些字母本身有没有自带这种用于排序的东西呢？
答案是有的，没错就是ascii
我们可以采用空间换时间的方法，每当遍历一个单词的时候，首先申请26个空间的数组，并且都置为0，然后根据出现的字母对应的数组值执行**+1**操作，遍历所有字母之后转换为字符串作为判断的识别符，你会发现，字母异位词对应的识别符是相同的，这样我们就在O(n)的时间里为互为字母异位词的单词设置了相同的识别符。
那为什么我们会想到这么做呢？
我们一起想想，排序的作用是什么，也就是让互为字母异位词的单词的字母按顺序排列作为识别符，这样相同识别符的就是字母异位词。但是时间复杂度有点高。
然后我们就在想，要是能不需要和其他字母比较，直接把字母放在他该放的位置就好了。
这样时间复杂度就低了，上面的话也就说O(1)的时间把字母放在该放的地方，这个概念有点熟悉呀，这不就是hash吗！
那怎么才能O(1)呢，这时候我们又想起来字母是有ascii码的，这说明可以根据ascii码做一下，于是我们就想到了用数组直接做个表，存储下字母出现的次数，然后最后直接判断识别符是否相同就可以了。
或则换一个思路，字母异位词有一个特性，就是字母出现的频率是相同的，只需要把这个频率记录下来，这个题就做出来了。
代码实现
排序做法
class Solution {
public String getSort(String word) {
char[] word_chars=word.toCharArray();
for(int i=0;i<word_chars.length;i++){
char tmp=' ';
for(int j=word_chars.length-1;j>i;j--){
if(word_chars[j]<word_chars[j-1])
{
tmp=word_chars[j];
word_chars[j]=word_chars[j-1];
word_chars[j-1]=tmp;
}
}
}
return new String(word_chars);
}
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map=new HashMap<String,List<String>>();
for (String str:strs){
if(!map.containsKey(getSort(str))){
map.put(getSort(str),new LinkedList<String>());
}
map.get(getSort(str)).add(str);
}
return new LinkedList(map.values());
}
}hash做法
class Solution {
public String getSort(String word) {
char[] chars = new char[27];
for (int i = 0; i < 26; i++) {
chars[i] = '0';
}
for (int i = 0; i < word.length(); i++) {
int ascii = word.charAt(i);
chars[ascii - 97]++;
}
return new String(chars);
}
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> stringListHashMap = new HashMap<>();
LinkedList<List<String>> lists = new LinkedList<>();
for (String str : strs) {
String str_sort = getSort(str);
if (!stringListHashMap.containsKey(str_sort))
stringListHashMap.put(str_sort, new LinkedList<String>());
stringListHashMap.get(str_sort).add(str);
}
for (String s : stringListHashMap.keySet()) {
List<String> strings = stringListHashMap.get(s);
lists.add(strings);
}
return lists;
}
}总结
感觉还是要找规律，一想到字母频率的问题，其实这个题就做出来了。