LeetCode : 49. Group Anagrams 分组字符串

冷不防 2021-06-24 16:11 339阅读 0赞

**试题**  
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.  
**代码**  
对字符排序后保证分到同一组，然后hash记录位置。

class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
            List<List<String>> out = new ArrayList<List<String>>();
            int ind=0;
            HashMap<String,Integer> has = new HashMap<>();
            for(String s : strs){
                char[] schar = s.toCharArray();
                Arrays.sort(schar);
                String ssort = Arrays.toString(schar);
                if(has.containsKey(ssort)){
                    out.get(has.get(ssort)).add(s);
                }else{
                    List<String> tmp = new ArrayList<>();
                    tmp.add(s);
                    out.add(tmp);
                    has.put(ssort,ind++);
                }
            }
            return out;
        }
    }

class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
            if (strs.length == 0) return new ArrayList();
            Map<String, List> ans = new HashMap<String, List>();
            for (String s : strs) {
                char[] ca = s.toCharArray();
                Arrays.sort(ca);
                String key = String.valueOf(ca);
                if (!ans.containsKey(key)) ans.put(key, new ArrayList());
                ans.get(key).add(s);
            }
            return new ArrayList(ans.values());
        }
    }

另外一种就是对字符进行统计，这样就不需要排序了。

class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
            if (strs.length == 0) return new ArrayList();
            Map<String, List> ans = new HashMap<String, List>();
            int[] count = new int[26];
            for (String s : strs) {
                Arrays.fill(count, 0);
                for (char c : s.toCharArray()) count[c - 'a']++;
    
                StringBuilder sb = new StringBuilder("");
                for (int i = 0; i < 26; i++) {
                    sb.append('#');
                    sb.append(count[i]);
                }
                String key = sb.toString();
                if (!ans.containsKey(key)) ans.put(key, new ArrayList());
                ans.get(key).add(s);
            }
            return new ArrayList(ans.values());
        }
    }

LeetCode : 49. Group Anagrams 分组字符串

发表评论取消回复

还没有评论，来说两句吧...

相关阅读