Skip to content

Latest commit

 

History

History
110 lines (96 loc) · 3.63 KB

A-20191024-字母异位词分组.md

File metadata and controls

110 lines (96 loc) · 3.63 KB
Raw
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/*
 * @lc app=leetcode.cn id=49 lang=java
 *
 * [49] 字母异位词分组
 *
 * https://leetcode-cn.com/problems/group-anagrams/description/
 *
 * algorithms
 * Medium (58.55%)
 * Likes:    199
 * Dislikes: 0
 * Total Accepted:    32.7K
 * Total Submissions: 55.5K
 * Testcase Example:  '["eat","tea","tan","ate","nat","bat"]'
 *
 * 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
 * 
 * 示例:
 * 
 * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
 * 输出:
 * [
 * ⁠ ["ate","eat","tea"],
 * ⁠ ["nat","tan"],
 * ⁠ ["bat"]
 * ]
 * 
 * 说明：
 * 
 * 
 * 所有输入均为小写字母。
 * 不考虑答案输出的顺序。
 * 
 * 
 */

// @lc code=start
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {


 //       List<List<String>> res = new ArrayList<List<String>>();
        HashMap<String,List> map = new HashMap<String,List>();
        for (String str : strs) {
            char[] key = str.toCharArray();
            Arrays.sort(key);
            // String k = String.valueof(key);
            String k = new String(key);

       //官解的代码太优雅了，if else可以简单提取公共部分和非公共部分，把非公共部分放入if中单独处理。如下面这段代码，公共部分就是要往map中某个key对应的List值中添加元素，有差异的地方是如果key不存在，可以先执行map.put(key,new ArrayList())，添加一个空的list作为对应key的值，代码就可以简化成两行。。。
        //     if( map.containsKey(k)){
        //         map.get(k).add(str);
        //     } else {
        //         List<String> list = new ArrayList<String>();
        //         list.add(str);
        //         map.put(k, list);
        //     }
        // }
             if( !map.containsKey(k)) map.put(k, new ArrayList());
             map.get(k).add(str);

        }
        //map.value返回的是一个Collection，可以在新建ArrayList的时候直接用来初始化。
        // for (String key : map.keySet()) {
        //     res.add(map.get(key));
        // }
        // return res;
        return new ArrayList(map.values());
        
    }
}
// @lc code=end

Leetcode官解中的按计数分类的代码，省去了将字符串排序的过程，对每个字符串仅记录26个字母出现的顺序。将时间复杂度由O(NKlogK) 减少为O(NK), 其中N为strs的长度，K为strs中最长的字符串的长度。

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']++;

            //key为以#为分隔符分隔出每个字母出现的次数，包含26个#与26个数字，每个数字对应一个字母出现的次数，如字符串abbccc的key为#1#2#3#0#0.....#0一共有23个0。
            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());
    }
}