49、同分异构字符串分类

leetcode 哈希

Created At : 2020-07-26 00:19

Count:604 Views 👀 :

Comment:

题目
1. 示例:
分析：字符串分类的题
1. 解法1:
2. 解法2:

题目

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:

[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

分析：字符串分类的题

题目中有很多个word,不同的word中的字符可能是一样的，需要归为一类，可以采用哈希表存储同一类异构字符串的值。

解法1:

利用HashMap，存储key
将每一个字符串拆分成字符数组，然后，排序，在组装成字符串，这样同字符异构的字符串就变成一样的了
利用key就可以查找含有同样字符的字符串了

// java Map API使用注意：getOrDefault(key,default) 的 返回值需要重新put到map中去，否则Map中不存在对应的key-value。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);// 字典排序
            String key = new String(array);// 构造key,
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        // 构造二维list并返回
        return new ArrayList<List<String>>(map.values());
    }
}

解法2:

将字符串拆分，然后，将字符串按照一定规则，获得其独有的特点（构造hashcode）
- 统计字符串中每个字母的个数，然后append每个字母的个数，同时加上用特殊字符的分隔符
同样利用HashMap的特点

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 空字符集处理
        if (strs.length == 0) return new ArrayList<List<String>>();
        // 结果集
        Map<String,List<String>> map = new HashMap<String,List<String>>();
        int[] count = new int[26];
        for (int i = 0;i < strs.length;i++) {
            // 构造唯一的指纹
            Arrays.fill(count,0);
            for(char c :strs[i].toCharArray()) count[c-'a']++;// 统计字符
            
            StringBuilder sb = new StringBuilder("");
            for (int j = 0;j < 26;j++) {// 构造字符串
                sb.append("$");
                sb.append(count[j]);
            }
            String key = sb.toString();// 获得key
            if (!map.containsKey(key)) map.put(key,new ArrayList<String>());
            map.get(key).add(strs[i]);
        }
        
        
        return new ArrayList<List<String>>(map.values());
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com