61 lines
1.9 KiB
Java
61 lines
1.9 KiB
Java
|
package com.zerroi.leetcode.Three19;
|
||
|
|
||
|
import java.util.*;
|
||
|
|
||
|
public class GroupAnagrams {
|
||
|
public static void main(String[] args) {
|
||
|
SolutionSecond solutionSecond = new SolutionSecond();
|
||
|
List<List<String>> res = solutionSecond.groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});
|
||
|
res.forEach(System.out::println);
|
||
|
}
|
||
|
}
|
||
|
|
||
|
class SolutionSecond {
|
||
|
public List<List<String>> groupAnagrams(String[] strs) {
|
||
|
if (strs.length <= 1) Arrays.asList(strs);
|
||
|
|
||
|
List<List<String>> res = new ArrayList<>();
|
||
|
List<String> path = new ArrayList<>();
|
||
|
boolean[] walked = new boolean[strs.length];
|
||
|
for (int i = 0; i < strs.length; i++) {
|
||
|
if (walked[i]) continue;
|
||
|
path.add(strs[i]);
|
||
|
for (int j = i + 1; j < strs.length; j++) {
|
||
|
if (isAnagram(strs[i], strs[j])) {
|
||
|
path.add(strs[j]);
|
||
|
walked[j] = true;
|
||
|
}
|
||
|
}
|
||
|
res.add(new ArrayList<>(path));
|
||
|
path.clear();
|
||
|
}
|
||
|
return res;
|
||
|
}
|
||
|
|
||
|
private boolean isAnagram(String s, String t) {
|
||
|
if (s.length() != t.length()) return false;
|
||
|
int[] count = new int[26];
|
||
|
for (char c : s.toCharArray()) {
|
||
|
count[c - 'a']++;
|
||
|
}
|
||
|
for (char c : t.toCharArray()) {
|
||
|
count[c - 'a']--;
|
||
|
if (count[c - 'a'] < 0) return false;
|
||
|
}
|
||
|
return true;
|
||
|
}
|
||
|
|
||
|
public List<List<String>> groupAnagrams(String[] strs, int a) {
|
||
|
Map<String, List<String>> map = new HashMap<>();
|
||
|
for (int i = 0; i < strs.length; i++) {
|
||
|
char[] array = strs[i].toCharArray();
|
||
|
Arrays.sort(array);
|
||
|
String str = new String(array);
|
||
|
List<String> list = map.getOrDefault(str, new ArrayList<>());
|
||
|
list.add(strs[i]);
|
||
|
map.put(str, list);
|
||
|
}
|
||
|
return new ArrayList<>(map.values());
|
||
|
}
|
||
|
}
|