76 lines
1.7 KiB
Markdown
76 lines
1.7 KiB
Markdown
# 字母异位词分组
|
||
|
||
## 题目
|
||
|
||
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
|
||
|
||
*字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。*
|
||
|
||
示例 1:
|
||
|
||
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
|
||
|
||
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
|
||
|
||
解释：
|
||
|
||
在 strs 中没有字符串可以通过重新排列来形成 "bat"。
|
||
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
|
||
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。
|
||
示例 2:
|
||
|
||
输入: strs = [""]
|
||
|
||
输出: [[""]]
|
||
|
||
示例 3:
|
||
|
||
输入: strs = ["a"]
|
||
|
||
输出: [["a"]]
|
||
|
||
|
||
|
||
提示：
|
||
|
||
1 <= strs.length <= 104
|
||
0 <= strs[i].length <= 100
|
||
strs[i] 仅包含小写字母
|
||
|
||
## 思路
|
||
|
||
- 异位词
|
||
- 对异位词的字符列表排序，最终是一样的
|
||
- 哈希
|
||
- `HashMap<String, List<String>>`
|
||
- 键：排序后字符串
|
||
- 值：字符串列表
|
||
- 过程
|
||
- 排序
|
||
- 判断是否存在
|
||
- 存在加入对应列表
|
||
- 不存在新增键
|
||
|
||
|
||
## 代码
|
||
|
||
```java
|
||
class Solution {
|
||
public List<List<String>> groupAnagrams(String[] strs) {
|
||
// New
|
||
Map<String, List<String>> map = new HashMap<>();
|
||
// Traverse
|
||
for (String str : strs) {
|
||
// Get Key
|
||
char[] array = str.toCharArray();
|
||
Arrays.sort(array);
|
||
String key = new String(array);
|
||
// Get Value
|
||
List<String> list = map.getOrDefault(key, new ArrayList<String>());
|
||
list.add(str);
|
||
map.put(key, list);
|
||
}
|
||
return new ArrayList<List<String>>(map.values());
|
||
}
|
||
}
|
||
``` |