n个字符串的交集

Question

我正在编写一个程序，以查找n个字符串的交集字符。我编写了以下代码：

import java.util.ArrayList;
import java.util.Scanner;
public class TestJoin {

public static void main(String[] args) {

  Scanner sc=new Scanner(System.in);


      int n=sc.nextInt();  // no of strings
      String s1 =sc.next().toLowerCase();
      ArrayList<Character> set1 = new ArrayList<Character>();
      while(n-->1)
      {
          String s2 =sc.next().toLowerCase();
          ArrayList<Character> set2 = new ArrayList<Character>();
          for(char c : s1.toCharArray()) {
                set1.add(c);
            }
          for(char c : s2.toCharArray()) {
                set2.add(c);
            }
          set1.retainAll(set2);
          for(char c : set1)
          {
              s1=Character.toString(c);
          }
      }
       for(char c :set1)
      System.out.println(c);


  }
}

当我尝试打印字符时，输出结果不正确。

输入-

 3
 aabcde
 abazx
 yuabna

期望输出：aab 实际输出：aabb

- TOP 10

---

你没有提出问题！ - Nicholas K

“intersection” 是什么意思？从给定的输入中如何得到 aab？为什么不是 aba 或 baa？ - Code-Apprentice

也请提供一个完整的、可以无误编译的代码示例。 - Code-Apprentice

@Code-Apprentice 顺序不重要（aab，aba，baa都是相同的）。交集指所有字符串中共同的字符。 - TOP 10

我建议你退后一步，用文字描述解决问题所需的步骤。这将帮助你弄清如何修改代码以遵循这些步骤。然后，如果你仍然得到错误的输出，你可以使用一些调试技巧来找到问题。请参阅 https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ 了解有关如何调试代码的一些技巧。 - Code-Apprentice

Answer 1

使用单独的方法通常可以使问题更小且更容易解决。

我建议您首先创建一个计算两个字符串交集的方法，然后在while循环中使用它来计算传入字符串与当前交集的交集。

我尝试保持您的逻辑，并编写了自己的保留循环，因为我不确定List.retainAll的作用。

该方法计算两个字符串的交集：最初的回答

private static String intersectionOf(String s1, String s2) {
    List<Character> list1 = new ArrayList<>();
    for(char c : s1.toCharArray()) {
        list1.add(c);
    }
    List<Character> list2 = new ArrayList<>();
    for(char c : s2.toCharArray()) {
        list2.add(c);
    }

    StringBuilder intersection = new StringBuilder();
    for(Character c : list1) {
        if(list2.contains(c)) {
            intersection.append(c);
            list2.remove(c); // remove it so it is not counted twice
        }
    }
    return intersection.toString();
}

你现在可以在循环中使用它，逻辑看起来简单得多。最初的回答。

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);

    int n = sc.nextInt();  // no of strings

    String result = sc.next().toLowerCase();
    String s;
    while(n-- > 1) {
        s = sc.next().toLowerCase();
        result = intersectionOf(result, s);
    }
    for(char c : result.toCharArray())
        System.out.println(c);
}

- Bentaye

---

如果您的字符串很长且数量众多，但交集相对较小，则此方法具有速度优势。 - biziclop

Answer 2

public static void intersect(String... input) {
    HashMap<Character, Integer> mins = new HashMap<Character, Integer>();
    HashMap<Character, Integer> current = new HashMap<Character, Integer>();

    for (String s : input) {
        current.clear();
        char[] chars = s.toCharArray();
        //Next loop remembers how many time every char occurs
        for (char c : chars) {
            Integer value = current.get(c);
            if (value == null) value = 0;
            current.put(c, value + 1);
        }

        if (mins.size() == 0) {
            mins.putAll(current); //First time just copy
        } else {
           //If not the first time then compare with previous results
            for (Character c : mins.keySet()) {
                Integer min = mins.get(c);
                Integer cur = current.get(c);
                if (cur != null) {
                    if (min > cur) {
                        //If has less than all previous
                        mins.put(c, cur);
                    }
                } else {
                    //If doesn't have at all
                    mins.put(c, 0);
                }
            }
        }
    }

    //Output every char that occurs in every string
    //more that 0 times
    for (Character c : mins.keySet()) {
        Integer count = mins.get(c);
        for (int i = 1; i <= count; i++) {
            System.out.print(c);
        }
    }
}

调用：

public static void main(String[] args) {
   intersect("aabcdeabazx", "abazx", "yuabna");
}

您可以将参数更改为以数组形式传递。此算法的计算复杂度约为O(n)。

- Ken Bekov

---

这绝对不是O(n)，因为你在这里使用了嵌套循环。同时，最好不要改变OP的代码太多。 - Nicholas K

@NicholasK说，O通常表示复杂度增长函数。随着输入数据的增加，该算法的增长函数是线性的（至少非常接近线性）。因此，复杂度为O（n）。 - Ken Bekov

@NicholasK 第二个循环不会超过26（对于英文字母的小写字母），无论我们输入多少个字符串。 - Ken Bekov