49. 字母异位词分组
程序员文章站
2022-07-08 16:00:39
...
1.题目
2.解法
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> hash = new HashMap<>();
for (int i = 0 ; i < strs.length ; i++) {
char[] ctmp = strs[i].toCharArray();
Arrays.sort(ctmp);
// HashMap中没有就新建,有就直接添加
String key = String.valueOf(ctmp);
if (hash.containsKey(key)) {
hash.get(key).add(strs[i]);}
else {
List<String> val = new ArrayList<String>();
val.add(strs[i]);
hash.put(key, val); } }
return new ArrayList<List<String>>(hash.values());}}
Arrays.sort排序的时间复杂度为O(slogs), 外面还有n次循环,总共为nslogs,s为字符串的长度。
空间复杂度为O(ns),hashmap保存了每个字符串
3.思考
@1:我对ArrayList操作不熟,还有Arrays.sort()…得赶紧学习了
@2、一个字符串会有原始字符,所以只要知道原始字符,
原始字符下一级对应所有的情况,所以这里应该用HashMap
@3、原始字符串可以用Array.sort()排序得到
下一篇: maven依赖关系中Scope的作用