牛的基因组学

题目

链接：1776. 牛的基因组学 - AcWing题库

农夫约翰拥有 N 头有斑点的牛和 N 头没有斑点的牛。

他刚刚完成了牛遗传学课程，他确信奶牛上的斑点是由牛基因组突变引起的。

农夫约翰花了大价钱对他的奶牛的基因组进行了测序。

每个基因组都是一个由四个字符 A,C,G,T 构成的长度为 M 的字符串。

当他统计得到的奶牛的基因组序列时，可以得到一个如下所示的表：（此时，N=3）

位置 :    1 2 3 4 5 6 7 ... M

斑点牛 1: A A T C C C A ... T
斑点牛 2: G A T T G C A ... A
斑点牛 3: G G T C G C A ... A

普通牛 1: A C T C C C A ... G
普通牛 2: A C T C G C A ... T
普通牛 3: A C T T C C A ... T

通过仔细观察该表，他发现通过位置 2 的字符足以判断奶牛是否存在斑点。

也就是说，仅通过查看这个位置上的字符，农夫约翰就可以判断他的哪些奶牛有斑点，哪些没有斑点。（在这里，A 和 G 表示有斑点，C 表示无斑点，T 无关紧要，因为没有任何一头牛的第二个位置上的字符是 T）

位置 1 上的字符不足以判断奶牛是否存在斑点，因为 A 既可以表示有斑点也可以表示无斑点。

给定约翰的奶牛的基因组序列列表，请你计算可以单独用来判断奶牛是否存在斑点的位置的数量。

代码

import java.util.*;


public class Main {
    static int N = 100010;
    static int n, m, ans = 0;
    static String[] q = new String[110];
    static TreeSet<Integer>[] set = new TreeSet[110];
    public static boolean check(int k)
    {
        for(int i = 1; i <= n; i ++)
        {
            int t = q[i].charAt(k) - 'A';
            if(set[k].contains(t))
                return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        m = inScanner.nextInt();
        String s;
        for(int i = 0; i < m; i ++)
            set[i] = new TreeSet<Integer>();
        for(int i = 1; i <= n; i ++)
        {
            s = inScanner.next();
            for(int j = 0; j < m; j ++)
                set[j].add(s.charAt(j) - 'A');
        }
        for(int i = 1; i <= n; i ++)
            q[i] = inScanner.next();
        for(int i = 0; i < m; i ++)
        {
            if(check(i))
                ans ++;
        }
        inScanner.close();
        System.out.println(ans);
    }
}