java - 在Java中将列表中的元素分组到不重复的子列表中

Question

我正在研究“分组字谜”。 问题陈述:给定一个字符串数组，将字谜组合在一起。

我可以对字谜进行分组，但我无法避免已经分组的字谜。我想避免重复。一个元素只能属于一个组。在我的代码中，一个元素属于多个组。

这是我的代码:

       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

组的显示顺序并不重要。显示方式并不重要。

偏好:请随意提交使用 HashMap 的解决方案，但我更喜欢看到不使用 HashMap 并使用 Java8 的解决方案

Answer 1

我还建议使用 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());

要生成排序的字符串键来对字谜进行分组，您可以查看 here了解更多解决方案。

结果是我提供的解决方案将是这样的:

[[eat, tea, ate], [bat], [tan, nat]]