【探索

admin管理员组

文章数量:1516870

【探索

解题的关键思想就是将字符串建立起无关于字母顺序，只关于字母个数的唯一映射关系，这样 ，对于同一组符合要求的字符串，则它们的映射都是一样的，以此作为分组的依据。

具体的解题方法，暂时想到了两种。

1、将字符串映射为字母+数字的组合，如 a1b2c3，这样是符合上述条件的。

public static List<List<String>> groupAnagrams(String[] strs) {if (strs==null||strs.length<1) return null;List<List<String>> lists = new ArrayList<>();//map 用于存储映射，key 代表映射关系，value 代表在 lists 中的 indexMap<String, Integer> map = new HashMap<>();for (String s : strs) {int[] tmp = new int[26];//计算字母的个数for (int i = 0, l = s.length(); i < l; i++) {tmp[s.charAt(i)-'a']++;}StringBuilder stringBuilder = new StringBuilder();//映射为 字母+数字的组合，如 a1b2c3for (int i = 0; i < 26; i++) {if (tmp[i] > 0) {char c = (char) ('a' + i);//"" 是为了防止 c 被强制转换为 int 类型然后与 tmp[i] 相加在一起，这样就影响 key 值的唯一性stringBuilder.append(""+c + tmp[i]);}}String key = stringBuilder.toString();if (map.containsKey(key)) {lists.get(map.get(key)).add(s);} else {List<String> list = new ArrayList<>();list.add(s);map.put(key, lists.size());lists.add(list);}}return lists;
}

2、第二种思路就是将字符串内的字母进行排序，那么相同组合的排序后的结果肯定是一样，同样符合上述条件。

摘录自 LeetCode 答案集。

public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String str : strs) {char[] chars = str.toCharArray();Arrays.sort(chars);String key = new String(chars);if (!map.containsKey(key)) {map.put(key, new ArrayList<>());}map.get(key).add(str);}return new ArrayList<>(map.values());
}

本文标签： 探索