今日算法之_51_字母异位词分组
前言
Github:https://github.com/HealerJean
1、字母异位词分组
给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
1.1、解题思路
遍历这个数组,然后将每个字符串内部的char进行排序。接着将这个排好序的字符串作为key放入数组中,value为同属性的字符串集合
1.2、算法
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
List<List<String>> ret = new ArrayList<>();
for (int i = 0 ; i < strs.length ; i++){
String string = strs[i] ;
char[] characters = string.toCharArray();
Arrays.sort(characters);
if (map.containsKey(String.valueOf(characters))){
map.get(String.valueOf(characters)).add(string);
}else {
List<String> list = new ArrayList<>();
list.add(string);
map.put(String.valueOf(characters), list);
}
}
for (Object key: map.keySet()){
ret.add(map.get(key));
}
//return new ArrayList<>(map.values());
return ret;
}
1.3、测试
@Test
public void test(){
String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
System.out.println(groupAnagrams(strs));
}
控制台:
[[eat, tea, ate], [bat], [tan, nat]]