DNA序列

[编程题]DNA序列

热度指数：11207 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

牛牛又从生物科研工作者那里获得一个任务,这次牛牛需要帮助科研工作者从DNA序列s中找出最短没有出现在DNA序列s中的DNA片段的长度。
例如:s = AGGTCTA

序列中包含了所有长度为1的('A','C','G','T')片段,但是长度为2的没有全部包含,例如序列中不包含"AA",所以输出2。

注：长度为2的全部DNA片段有"AA"、"AC"、"AG"、"AT"、"CA"、"CC"、"CG"、"CT"、"GA"、"GC"、"GG"、"GT"、"TA"、"TC"、"TG"和"TT"，共16种。

输入描述:

输入包括一个字符串s,字符串长度length(1 ≤ length ≤ 2000),其中只包含'A','C','G','T'这四种字符。

输出描述:

输出一个正整数,即最短没有出现在DNA序列s中的DNA片段的长度。

示例1

输入

AGGTCTA

输出

示例2

输入

ACGT

输出

示例3

输入

AACAGATACCGCTGGTCTT

输出

算法知识视频讲解

牛客题解官

发表于 2020-06-05 17:48:20

精华题解 DNA序列题目难度：中等知识点：数学逻辑、宽度优先遍历方法一采用宽度优先遍历，得到长度为i的子串的所有排列，比较字符串中是否存在全部子串，若全部存在，则继续下一个长度的子串的遍历，否则，i即为字符串中没有包含所有该长度的子串，输出i，循环结束。 import java.util.Scanne 展开全文