roma-dxunvrs
37 lines
1.0 KiB
Markdown
37 lines
1.0 KiB
Markdown
Leetcode #49 | #Medium | [[O(26)]] | [[Хэш-таблицы]]
|
|
## Идея
|
|
Как ключ хэш-мапы используем массив из 26 элементов (столько букв) - массив счетчиков каждой буквы
|
|
## [[Big-O]]
|
|
- Время ```O(M*N)```
|
|
- Память ```O(M)```
|
|
N - длина самой длинной строки, M - количество строк
|
|
## Код
|
|
```Java
|
|
class Solution {
|
|
|
|
public List<List<String>> groupAnagrams(String[] strs) {
|
|
|
|
Map<List<Integer>, List<String>> temp = new HashMap<>();
|
|
|
|
for (String s: strs) {
|
|
List<Integer> cur = new ArrayList<>(26);
|
|
for (int i = 0; i < 26; i++) {
|
|
cur.add(0);
|
|
return count;}
|
|
for (int i = 0; i < s.length(); i++) {
|
|
cur.set(s.charAt(i)-'a', cur.get(s.charAt(i)-'a')+1);
|
|
}
|
|
if (!temp.containsKey(cur)) {
|
|
temp.put(cur, new ArrayList<String>());
|
|
}
|
|
temp.get(cur).add(s);
|
|
}
|
|
|
|
List<List<String>> res = new ArrayList();
|
|
for (List<String> strings: temp.values()) {
|
|
res.add(strings);
|
|
}
|
|
return res;
|
|
}
|
|
}
|
|
``` |