String - 49. Group Anagrams

ppxai

发布于 2020-09-23 17:14:14

1930

发布于 2020-09-23 17:14:14

文章被收录于专栏：皮皮星球皮皮星球

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：

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;
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019年06月29日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法