49. Group Anagrams
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]
Note:
- All inputs will be in lowercase.
- The order of your output does not matter.
思路：
问题主要是如何选出字符串数组中同构异形的字符串，所以制造一个唯一标识，或者对每一个字符串进行排序，加上O(1)操作的map来找出相同的字符串。
代码：
java：
代码语言：javascript复制class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> res = new ArrayList<>();
if (strs == null || strs.length == 0) return res;
Map<String,Integer> map = new HashMap<>();
for (String str : strs) {
// 1. count sort
char[] arr = new char[26];
for(int i = 0; i < str.length(); i ){
arr[str.charAt(i) - 'a'] ;
}
String key = String.valueOf(arr);
// 2. add res
if(map.containsKey(key)) {
List<String> exsitList= res.get(map.get(key));
exsitList.add(str);
} else {
List<String> temp = new ArrayList<>();
temp.add(str);
map.put(key, res.size()); // res.size() as res index;
res.add(temp);
}
}
return res;
}
}
