Group Anagrams List
Given an array of strings, group anagrams together.
For example, given: [eat
, tea
, tan
, ate
, nat
, bat
],
Return:
[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]
Note:
For the return value, each inner list's elements must follow the lexicographic order.
All inputs will be in lower-case.
Solution
Anagrams指几个string有相同的字符,但不同的字符顺序。所以一个有效的检查方法是:当两个string排序以后相同,则它们是anagrams。可以使用一个hash table,string s的key是它自己排序后的string,这样anagrams会有相同的key。用一个vector<int>
来记录相同key的string在input vector<string>
中的index。最后扫描一遍hash table,当有两个或以上string有相同的key时,将它们输出到结果。
Complexity
时间复杂度 O(n),空间复杂度 O(n)
Code
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> rst = new ArrayList<List<String>>();
HashMap<String, List<String>> map = new HashMap<String, List<String>>();
Arrays.sort(strs);
for(int i = 0; i < strs.length; i++) {
char[] strChar = strs[i].toCharArray();
Arrays.sort(strChar);
String str = new String(strChar);
if(map.containsKey(str)) {
map.get(str).add(strs[i]);
}
else {
List<String> list = new ArrayList<String>();
list.add(strs[i]);
map.put(str, list);
}
}
for(List<String> val : map.values()) {
rst.add(val);
}
return rst;
}
String sortChars(String s){
char[] content = sortChars.toCharArray();
Arrays.sort(content);
return new String(content);
}
}