染色体上有很多基因,你的生物信息学朋友想要检查一个特定的染色体是否有一系列的基因。基因发生的顺序很重要。你想在这件事上帮助你的朋友。他给你n条染色体和一系列他想要检查的基因。帮助他确定这些基因是否以给定的顺序存在于染色体中。
因为你不是生物系的学生,他让你变得更容易了。他用ASCII中的字母、数字或特殊字符来代表基因。空格不代表基因。
示例
如果染色体是abdfgc
,而他要查询的基因是abc
,这些基因在染色体中(以正确的顺序)存在(用粗体标记)。a*b*dfg*c*
。但是,如果查询是bca
,则这在染色体中没有以正确的顺序出现。
输入
第一行输入由一个整数n
组成,它是测试用例的数量。
每个测试用例由两行输入组成:
如果染色体-基因对的输出是“是”的,如果这些基因按照顺序被包含在染色体中,而不是“否”的话。输出应该有包含“是/否”的n行。
约束
1 <= n <= 10000
1 <= |chromosome| <100
1 <= |gene| < |chromosome|
样本输入
4
12sd78f
sf
12345efd
1e3d
ijkfgds
jkf
1111456
116
样本输出
YES
NO
YES
YES
码
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class solution {
private static String checkGem(String ch, String gem) {
int prevIndex = 0;
for(int n=0; n < gem.length(); n++) {
if(ch.indexOf(gem.charAt(n), prevIndex)==-1) {
return "NO";
}
else {
prevIndex = ch.indexOf(gem.charAt(n), prevIndex);
}
}
return "YES";
}
public static void main(String args[]) throws Exception {
//Scanner sc = new Scanner(System.in);
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String test = br.readLine();
int t = Integer.parseInt(test);
for(int i=0; i<t; i++) {
String ch = br.readLine();
String gem = br.readLine();
ch = ch.replaceAll("\\s","");
gem = gem.replaceAll("\\s","");
String ans = checkGem(ch, gem);
System.out.println(ans);
}
}
}
发布于 2018-11-22 10:08:49
您的代码中有一个bug。您可以尝试这个测试用例:
1
a
aaaaa
这个应该是“否”,但是您的代码输出是“是”。
问题是您需要提前处理prevIndex
,它应该是:
prevIndex = ch.indexOf(gem.charAt(n), prevIndex) + 1;
https://stackoverflow.com/questions/53435907
复制相似问题