java - 在Java中将列表中的元素分组到子列表中而不重复
问题描述
我正在研究“分组字谜”。问题陈述:给定一个字符串数组,将字谜组合在一起。
我可以对字谜进行分组,但我无法避免已经分组的字谜。我想避免重复。一个元素只能属于一个组。在我的代码中,一个元素属于多个组。
这是我的代码:
public class GroupAnagrams1 {
public static void main(String[] args) {
String[] input = {"eat", "tea", "tan", "ate", "nat", "bat"};
List<List<String>> result = groupAnagrams(input);
for(List<String> s: result) {
System.out.println(" group: ");
for(String x:s) {
System.out.println(x);
}
}
}
public static List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new ArrayList<List<String>>();
for(int i =0; i < strs.length; i++) {
Set<String> group = new HashSet<String>();
for(int j= i+1; j < strs.length; j++) {
if(areAnagrams(strs[i], strs[j])) {
group.add(strs[i]);
group.add(strs[j]);
}
}
if(group.size() > 0) {
List<String> aList = new ArrayList<String>(group);
result.add(aList);
}
}
return result;
}
这是检查两个字符串是否是字谜的方法。
private static boolean areAnagrams(String str1, String str2) {
char[] a = str1.toCharArray();
char[] b = str2.toCharArray();
int[] count1 = new int[256];
Arrays.fill(count1, 0);
int[] count2 = new int[256];
Arrays.fill(count2, 0);
for(int i = 0; i < a.length && i < b.length; i++) {
count1[a[i]]++;
count2[b[i]]++;
}
if(str1.length() != str2.length())
return false;
for(int k=0; k < 256; k++) {
if(count1[k] != count2[k])
return false;
}
return true;
}
}
预期输出:
group:
tea
ate
eat
group:
bat
group:
tan
nat
实际输出:
group:
tea
ate
eat
group:
tea
ate
group:
tan
nat
显示组的顺序无关紧要。它的显示方式无关紧要。
偏好:请随意提交使用 HashMaps 的解决方案,但我更喜欢看到不使用 HashMaps 和使用 Java8 的解决方案
解决方案
我也建议为此使用 java Streams。因为您不希望这是另一种解决方案:
public static List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> result = new ArrayList<>();
for (String str : strs) {
boolean added = false;
for (List<String> r : result) {
if (areAnagrams(str, r.get(0))) {
r.add(str);
added = true;
break;
}
}
if (!added) {
List<String> aList = new ArrayList<>();
aList.add(str);
result.add(aList);
}
}
return result;
}
您的解决方案中的问题是您将每次迭代都提前了一步,因此您只需生成不完整的组["tea", "ate"]
而不是["bat"]
.
我的解决方案使用不同的方法来检查您是否有一个组,其中第一个单词是搜索单词的字谜。如果没有创建一个新组并继续前进。
因为我会使用Java Streams,正如我在开头所说的,这是我使用流的初始解决方案:
List<List<String>> result = new ArrayList<>(Arrays.stream(words)
.collect(Collectors.groupingBy(w -> Stream.of(w.split("")).sorted().collect(Collectors.joining()))).values());
要生成排序的字符串键以对字谜进行分组,您可以在此处查找更多解决方案。
结果是我提供的解决方案都是这样的:
[[eat, tea, ate], [bat], [tan, nat]]
推荐阅读
- javascript - 如何从 inJavaSCript 的数组中打印多个元素?
- android-studio - 如何将android studio上的相机旋转到肖像模式
- html - For Loop HTML/JS ,每周递减数字
- python-3.x - 添加第 23 行后如何超出范围?
- nginx - 我想通过http进行通信,但它更改为https
- flutter - 当在 Flutter quiz-app 中选择错误答案时,如何在按下按钮时更改按钮的颜色或在下方打印新消息?
- ssl - VerneMQ TLS 配置给出错误握手失败使用letsencrypt
- modelica - 为什么在函数中使用灵活的数组输入会在 OpenModelica 中引发翻译错误?
- swift - 快速传递数据委托和协议
- python - 使用适当格式更改 Tkinter 中的图标时出现问题